CODEWITHSUNDEEP
arraysalgorithm
sam_33
sam_33

Reputation: 595

Find repeated element in array

Consider array of INT of positive numbers:

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

Given: only one number is repeated, return number and positions with efficient algorithm.

Any ideas for efficient algorithms?

Upvotes: 0

Views: 2325

Answers (7)

Sri
Sri

Reputation: 4853

Use the hash-map to solve it :

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");
}

Time complexity : O(n)

Space complexity : O(n)

Upvotes: 0

Paddy3118
Paddy3118

Reputation: 4772

In an interview situation, I guess its your chance to ask around the question, for example, how many numbers? what range of numbers? you could state that an optimum algorithm could change depending.

That gives you a chance to show how you solve problems.

If the range of ints in the array is small enough then you could create another array to keep count of the number of times each integer is found then go linearly through the array accumulating occurrence counts, stopping when you get to an occurance count of two.

Upvotes: 1

Don Lun
Don Lun

Reputation: 2777

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;
}

This is a solution my friend provided. Thank you SETI from mitbbs.com

Upvotes: 0

Ekkehard.Horner
Ekkehard.Horner

Reputation: 38745

I'd try this:

  1. all elms of list have to be looked at (=> loop over the list)
  2. before the repeated elm is known, store elm => location/index in a hash/dictionary
  3. as soon as the second occurence of the repeated element is found, store its first postion (from the hash) and the current position in the result array
  4. compare further elms of list against the repeated elm, append found locations to the result array

in code:

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

Test run:

-------------------------------------------------
     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

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

Upvotes: 0

T.E.D.
T.E.D.

Reputation: 44804

Well, there probably is some trick (usually is). But just off the cuff, you should be able to sort the list (O(nlogn)). Then its just a matter of finding a number that is the same as the next one (linear search - O(n)). You'd have to sort it as tuples of values and original indices of course, so you could return that index you are looking for. But the point is that the upper bound on an algorithim that will do the job should be O(nlogn).

If you just go through the list linerally, you could take each index, then search through the rest of the list after it for a matching index. I think that's roughly equivalent to the work done in a bubble sort, so it would probably be O(n^2), but a simple one.

I really hate trick questions as interview questions. They are kind of like optical illusions: Either you see it or you don't, but it doesn't really say anything bad about you if you don't see the trick.

Upvotes: 0

James
James

Reputation: 5425

One possible solution is to maintain an external hash map. Iterate the array, and place the indices of values found into the hash map. When done, you now know which number was duplicated and the indices of the locations it was found at.

Upvotes: 4

Nikita Rybak
Nikita Rybak

Reputation: 68006

Hash will do just fine in here. Add numbers to it one by one, each time checking if number's already in there.

Upvotes: 0

Related Questions