leetcode: 배열 에서 중복 되 는 데이터
1219 단어 알고리즘
두 번 나타 나 는 모든 원 소 를 찾 습 니 다.
당신 은 어떠한 추가 공간 도 가지 않 고 O (n) 시간 복잡 도 에서 이 문 제 를 해결 할 수 있 습 니까?
예시:
:
[4,3,2,7,8,2,3,1]
:
[2,3]사고: 이런 횟수 를 구 하 는 문 제 는 우 리 는 추가 배열 로 계산 통 계 를 하 는 것 을 쉽게 생각 할 수 있다.그러나 제목 의 요구 에 부합 되 지 않 고 제목 의 요 구 는 추가 공간 을 사용 할 수 없다.제목 이 제시 한 은밀 한 조건 을 이용 할 수 있다. 바로 수조 의 값 의 범위 가 수조 의 크기 보다 작다 는 것 이다.그러면 우 리 는 배열 값 으로 아래 표 시 를 하고 배열 을 옮 겨 다 니 며 표 시 를 할 수 있다.두 번 의 요소 가 나타 나 는데 두 번 째 방문 할 때 표 시 된 것 이 바로 원 하 는 요소 입 니 다.
vector findDuplicates(vector& nums) { vector result; if(nums.size() == 0) { return result; } for(int i= 0 ; i < nums.size(); ++i) { int num = abs(nums[i]); if(nums[ num -1 ] > 0) //배열 의 경 계 를 넘 는 것 을 방지 하기 위해 서 는 1. 0 보다 적 게 빼 야 하 며, 이전에 한 번 방문 한 적 이 있다 는 것 을 의미한다. { nums[ num -1 ] = -1 * nums[num - 1]; } else { result.push_back(num); } } return result; }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
