Geek asks and answers

How to find all odd elements in an array in JAVA

I am trying to find all elements that occur an odd number of times in an array. I did a little work, but my code returns the correct answer if there is only one number that occurs an odd number of times. If there are two or more odd numbers that I cannot process. I understand that if we are bitwise XOR elements, we get one odd element. How can I improve it for multiple numbers?

Below is my code:

public class OddOccur {
    public int oddoccurence(int[] arr, int size) {
        int res = 0;
        int[] fin = new int[size];

        for (int i = 0; i < size; i++) {
            res = res ^ arr[i];

        }
        return res;
    }

    public static void main(String args[]) {
        int[] arr = { 2, 5, 5, 2, 2, 3, 3, 3 };

        int n = arr.length;
        OddOccur obj = new OddOccur();

        System.out.println("odd occuring element is:"
                + obj.oddoccurence(arr, n));
    }
}

Need help solving this problem!

+4
source share
9 answers
public int oddoccurence(int[] arr, int size);

-, , . , int. , .

public int[] oddOccurrences(int[] array);

-, . XOR "". XOR. , . :

  • .
  • .

:

// Map from numbers to counts. Assume the counts start at 0.
Map<Integer, Integer> counts;

for (number in array) {
    counts[number] += 1
}

// List of numbers that occur an odd number of items.
List<Integer> oddNumbers;

for (number, count in counts) {
    if (count % 2 != 0) {
        oddNumbers.add(number);
    }
}
+5

, .. .

, , , . , Set, , , .

- :

public int solution(int[] A){

    Set<Integer> unpaired = new HashSet<Integer>();
    for (int i = 0; i<A.length; i++){
        if (unpaired.contains(A[i])){
            unpaired.remove(new Integer(A[i]));
        }else{
            unpaired.add(A[i]);
        }
    }


    // all printed out values are odd
    for (Integer res : unpaired){
        System.out.println(res);
    } 
}
0

, , . , (, -, , -) , , . x , x , ( ),

0

HashMap:

 public int solution(int[] A) {

        HashMap<Integer, Integer> map = new HashMap<>();
        HashSet<Integer> val = new HashSet<>();
        for (int i=0; i<A.length; i++){
        if (map.get(A[i]) == null) {
            map.put(A[i], 1);
        } else map.put(A[i], map.get(A[i])+1);

        if (map.get(A[i])%2 == 1) 
            val.add(A[i]);
            else val.remove(A[i]);
        }

        Iterator<Integer> itr = val.iterator();  
        return itr.next();  

    }
0

100% . , , HashMap. HashMap O (1) , . , O (N), N - .

HashMap, , . HashMap . , .

import java.util.*;
class Solution {
    public int solution(int[] A) {
        int key;
        Map<Integer, Integer> unpaired = new HashMap<Integer, Integer>();
        for (int i = 0; i < A.length; i++){
            key  = A[i];
            Integer value = unpaired.get(key);
            if (value != null){
                unpaired.remove(key); // Remove by key
            }
            else{
                unpaired.put(key,0);
            }
        }
        for (Map.Entry<Integer, Integer> entry : unpaired.entrySet())
        {
            key =  entry.getKey();
        }
        return key;
    }
}
0

, Map - , - BitMap .

public static List<Integer> oddNumbers(int[] array, int size) {
        BitSet bitSet = new BitSet();
        for (int i = 0; i < size; i++) {
            bitSet.flip(array[i]);
        }

        List<Integer> resp = new ArrayList<>();
        for (int i = 0; i < bitSet.length(); i++) {
            if (bitSet.get(i)) {
                resp.add(i);
            }
        }
        return resp;
    }

:

@Test
public void test_oddNumbers() throws Exception {
    int[] arr = {2, 5, 5, 2, 2, 3, 3, 3, 1, 7, 8, 9, 9, 9};
    List<Integer> resp = oddNumbers(arr, arr.length);
    assertTrue(resp.size() == 6);
    assertTrue(resp.containsAll(Arrays.asList(1, 2, 3, 7, 8, 9)));
}
0

// 100% .

import java.util.Arrays;

{

public int solution(int[] A) {
    // write your code in Java SE 8

    Arrays.sort(A);

    int length = A.length;

    for (int i = 0, j = 1; i < length; i++) {
        if (j < length && A[i] == A[j]) {
            i++;
            j = j + 2;
        } else {
            return A[i];
        }
    }

    return 0;   
}

}

0

, xor . , .

0

.

public int oddoccurence(int []a){
    if(a.length==1){
        return a[0];
    }
    Arrays.sort(a);
    for(int i=0;i<a.length-1;){
        if(a[i]==a[i+1]){
            i+=2;
        }else{
            return a[i];
        }
    }
    return a[a.length-1];
}
-1

More articles:


All Articles