배열

Question

반복 요소를 찾기와 양수의 INT의 배열을 고려하십시오

{1,3,6,4,7,6,9,2,6,6,6,6,8} 

감안할 : 하나의 번호가 반복되고, 반환 번호와 효율적인 알고리즘에 위치.

효율적인 알고리즘에 대한 아이디어가 있으십니까?

Answer 1

해시가 여기에 적합합니다. 번호가 이미 하나씩 있는지 확인 할 때마다 하나씩 번호를 추가하십시오.

Answer 2

가능한 해법 중 하나는 외부 해시 맵을 유지하는 것입니다. 배열을 반복 해, 발견 된 값의 인덱스를 해시 맵에 배치합니다. 완료되면 중복 된 숫자와 발견 된 위치의 색인을 알 수 있습니다.

Answer 3

음, 아마도 약간의 트릭이 있습니다 (일반적으로). 그러나 팔목 바로 옆에서 목록을 정렬 할 수 있어야합니다 (O(nlogn)). 그런 다음 다음 숫자와 같은 숫자를 찾는 문제입니다 (선형 검색 - O(n)). 값과 원래 인덱스의 튜플로 정렬해야하므로 원하는 인덱스를 반환 할 수 있습니다. 그러나 요점은 작업을 수행 할 알고리즘의 상한이 O(nlogn)입니다.

목록을 순회하기 만하면 각 색인을 가져온 다음 나머지 목록에서 일치하는 색인을 검색 할 수 있습니다. 저는 이것이 버블 정렬에서 수행 된 작업과 대략 동일하다고 생각합니다. 따라서 이것은 아마도 O(n^2)이 될 것이지만, 간단한 것일 것입니다.

저는 인터뷰 질문으로 트릭을 싫어합니다. 그들은 착시 현상과 비슷합니다. 당신이 그것을 보든 그렇지 않든간에, 트릭을 보지 않으면 정말 나쁜 말을하지 않습니다.

Answer 4

나는이 시도 것 : 목록의

1. 모든 느릅 나무가 반복 느릅 나무가 알려지기 전에 (목록 이상 => 루프)
2. 에보고 할 필요가 저장 느릅 나무 => 위치/색인
3. 반복 요소의 두 번째 발생이 발견되면 해시의 첫 번째 위치와 결과 배열의 현재 위치를 저장합니다.
4. 반복되는 느릅 나무 결과 배열에 찾은 위치를 추가합니다.
코드

:

Function locRep(aSrc) 
    ' to find repeated elm quickly 
    Dim dicElms : Set dicElms = CreateObject("Scripting.Dictionary") 
    ' to store the locations 
    Dim aLocs : aLocs  = Array() 
    ' once found, simple comparison is enough 
    Dim vRepElm : vRepElm  = Empty 
    Dim nIdx 
    For nIdx = 0 To UBound(aSrc) 
     If vRepElm = aSrc(nIdx) Then ' repeated elm known, just store location 
     ReDim Preserve aLocs(UBound(aLocs) + 1) 
     aLocs(UBound(aLocs)) = nIdx 
     Else ' repeated elm not known 
     If dicElms.Exists(aSrc(nIdx)) Then ' found it 
      vRepElm = aSrc(nIdx) 
      ReDim aLocs(UBound(aLocs) + 2) 
      ' location of first occurrence 
      aLocs(UBound(aLocs) - 1) = dicElms(aSrc(nIdx)) 
      ' location of this occurrence 
      aLocs(UBound(aLocs) ) = nIdx 
     Else 
      ' location of first occurrence 
      dicElms(aSrc(nIdx)) = nIdx 
     End If 
     End If 
    Next 
    locRep = aLocs 
End Function 

테스트 실행 :

------------------------------------------------- 
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 
Src: 1 3 6 4 7 6 9 2 6 6 6 6 8 
Res: 2 5 8 9 10 11 
ok 

Src: 
Res: 
ok 

Src: 1 2 3 
Res: 
ok 

Src: 1 1 2 3 4 5 6 
Res: 0 1 
ok 

Src: 1 2 3 4 5 6 6 
Res: 5 6 
ok 

================================================= 

Answer 5

using namespace std; 
list<int> find_duplicate_idx(const vector<int>& A) 
{ 
hash_map<int, int> X; 
list<int> idx; 
for (int i = 0; i < A.size(); ++ i) { 
    hash_map<int, int>::iterator it = X.find(A[i]); 
    if (it != X.end()) { 
    idx.push_back(it->second); 
    idx.push_back(i); 
    for (int j = i + 1; j < A.size(); ++j) 
     if (A[j] == A[i]) 
     idx.push_back(j); 
    return idx; 
    } 
    X[A[i]] = i; 
} 
return idx; 
} 

이 내 친구가 제공하는 솔루션입니다. 감사합니다. SETI from mitbbs.com

Answer 6

인터뷰 상황에서 질문 수를 물어볼 기회를 생각해보십시오. 숫자의 범위는 무엇입니까? 당신은 최적의 알고리즘이 바뀔 수 있다고 말할 수 있습니다.

이렇게하면 문제를 해결하는 방법을 보여줄 수 있습니다.

배열의 int 범위가 충분히 작은 경우 각 정수가 발견 된 횟수를 유지하기 위해 다른 배열을 생성 한 다음 발생 횟수를 누적하는 배열을 통해 선형으로 이동하여 발생시 중지합니다 2의 카운트.

Answer 7

그것을 해결하기 위해 해시 맵을 사용

private int getRepeatedElementIndex(int[] arr) { 

    Map<Integer, Integer> map = new HashMap(); 
    // find the duplicate element in an array 
    for (int i = 0; i < arr.length; i++) { 
     if(map.containsKey(arr[i])) { 
      return i; 
     } else { 
      map.put(arr[i], i); 
     } 
    } 
    throw new RuntimeException("No repeated element found"); 
} 

시간 복잡도 : (n)이 O

공간의 복잡성을 : O는 (n)이