Как найти все нечетные элементы массива

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

John Kugelman
06 фев. 2014, в 01:00

Поделиться

//Это решение набрало 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;   
}

}

Ramesh J
04 фев. 2019, в 11:22

Поделиться

Я думаю, что использование 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)));
}

TongChen
12 янв. 2019, в 02:41

Поделиться

Этот раствор набрал 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;
    }
}

Omar Abid
12 янв. 2019, в 00:22

Поделиться

Вот мое решение с помощью 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();  

    }

0xalihn
02 авг. 2017, в 10:28

Поделиться

gurubelli
09 фев. 2017, в 21:42

Поделиться

Может быть, старый пост.. но вот мой ответ.

По моему мнению, нет необходимости подсчитывать числа числа, чтобы определить, является ли оно нечетным или нет. Пусть используется структура данных, такая как 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);
    } 
}

gipinani
24 май 2016, в 22:25

Поделиться

это будет хорошим решением для вашей проблемы.

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

Ahmed gouda
27 июнь 2016, в 22:29

Поделиться