Find an unpaired number in an array

I have an array that repeats all the elements except one:

int[] a={2,6,6,2,4,1,4};

      

How can I find an integer number of elements that is unpaired?

+4


source to share


3 answers


There are several approaches you can take:

  • Approach 1 - O (n log n): sort the array. Then we iterate over the elements of the sorted array, two at a time ( i=0

    , i=2

    etc.). When a[i]

    and are a[i+1]

    unequal; or when i+1 == a.length

    - you know you are not a[i]

    pathetic.
  • Approach 2 - O (n 2 ): iterating over the elements. For each element a[i]

    , iterate over the elements (in a nested loop) and see if this ever happens a[i] == a[j]

    as well i != j

    . If not, then it is not a[i]

    pathetic.
  • Approach 3 is O (m), where m is the difference between the largest and smallest elements (noting that m is [Omega; (n)): iterate over the elements, find the largest and smallest values โ€‹โ€‹of MIN

    and MAX

    . Create int[] b = new int[MAX-MIN+1]

    . Iterate over the elements again, incrementing b[a[i]-MIN]

    for each element. Then let's move on to b

    ; when you find b[j]==1

    , j

    unpathetic.

Note: You are using the term "whole number of elements", but this is not a real term. The above assumes you mean "integer element". If you really mean "element index", then only approach 2 can be used without modification. Set 3 will require a small adjustment, and Set 1 will require a large adjustment. (Of course, once you find a value that occurs only once, you can simply iterate over the array again to find the index of that value. If you still have the original order of the array.)




Edited to add: I don't know how I missed this before - I guess I'm not used to thinking about bitwise operations when writing Java - but actually the best solution is:

  • Approach 4 - O (n): Compute bit-XOR, of ^

    all array elements. This is an unpaired element. You can see that XOR is commutative and associative, so it is the 2^6^6^2^4^1^4

    same as 1^(2^2)^(4^4)^(6^6)

    ; and x^x

    always 0

    , so pairs always override any other. You can simply write:

    int result = 0;
    for(int i : a)
        result ^= i;
    
          

    to compute an unpaired element. (To get the index of the unmatched element, you iterate over the array again, looking result

    .)

+22


source


You can use the map to count how many times a number has been seen. There are undoubtedly better ways to do this, but it will work.



public static void main( String[] args ) {
    int[] a = { 2, 6, 6, 2, 4, 1, 4 };

    Map<String, Integer> counts = new HashMap<String,Integer>();

    String key;
    for ( int i : a ) {
        key = String.valueOf( i );
        if ( counts.containsKey( key ) ) {
            int count = counts.get( key );
            counts.put( key, ++count );
        }
        else {
            counts.put( key, 1 );
        }
    }

    for ( Map.Entry<String, Integer> entry : counts.entrySet() ) {
        if ( entry.getValue() < 2 ) {
            System.out.println( entry.getKey() + " does not have a pair" );
        }
    }
}

      

+1


source


Here I found a solution to find unpaired value of array An with complexity O (n ^ 2) enter image description here

0


source







All Articles