从具有奇数项的给定数组中找到不重复的整数

Question

试图用这段代码找出错误。这适用于小样本，但不适用于大量样本（虽然我手中没有大样本）。该解决方案适用于以下测试。private static final int[] A = {9,3,9,3,9,7,9};private static final int[] A2 = {9,3,9};private static final int[] A3 = {9,3,9,3,9,7,7,2,2,11,9};@Testpublic void test(){    OddOccurance oddOccurance =new OddOccurance();    int odd=oddOccurance.solution(A);    assertEquals(7,odd);}@Testpublic void test2(){    OddOccurance oddOccurance =new OddOccurance();    int odd=oddOccurance.solution(A2);    assertEquals(3,odd);}@Testpublic void test3(){    OddOccurance oddOccurance =new OddOccurance();    int odd=oddOccurance.solution(A3);    assertEquals(11,odd);}当一个数组给出奇数个整数时（除了一个整数，其他整数可以重复）。解决方案是找到不重复的整数。欢迎任何其他更好的想法（时间和空间优化）来实现这一点。  public int solution(int[] A) {    // write your code in Java SE 8    Map<Integer, List<Integer>> map = new HashMap<>();    int value = 0;    //iterate throught the list and for each array value( key in the map)    // set how often it appears as the value of the map    for (int key : A) {        if (map.containsKey(key)) {            map.get(key).add(value);        } else {            List<Integer> valueList = new ArrayList<>();            valueList.add(value);            map.put(key, valueList);        }    }    Set<Map.Entry<Integer, List<Integer>>> entrySet = map.entrySet();    //   en    for (Map.Entry<Integer, List<Integer>> entry : entrySet) {        if (entry.getValue().size() == 1) {            return entry.getKey();        }    }    return 0;}更新 查看失败的输出错误答案，预期为 0 42 错误答案，预期为 0 700似乎它甚至没有进入 for 循环，而只是返回 0

Answer 1

这是一个标准问题，如果实际陈述如下：

除一个之外的每个数字出现偶数次；剩余的数字出现一次。

解决方案是取xor所有数字。由于每个重复的数字都出现偶数次，它会自行取消。原因是它xor是可交换的：

a xor b xor c = a xor c xor b = c xor b xor a = etc.

例如，如果1, 2, 3, 1, 2

1 xor 2 xor 3 xor 1 xor 2 =

(1 xor 1) xor (2 xor 2) xor 3 =

0 xor 0 xor 3 =

3

Answer 2

如果没有实际的错误消息，很难知道为什么你的失败。无论如何，随着您的数组输入变得非常大，您的内部数据结构会相应地增长，但不需要这样做。取而代之的是一个数组Integer作为值，我们可以只使用一个Integer：

public int solution(int[] a) {

    Integer ONE = 1;

    Map<Integer, Integer> map = new HashMap<>();

    for (int key : a) {

        Integer value = (map.containsKey(key)) ? map.get(key) + ONE : ONE;

        map.put(key, value);

    }

    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {

        if (entry.getValue().equals(ONE)) {

            return entry.getKey();

        }

    }

    return -1;

}

我假设奇数数组长度要求是为了避免长度为 2 的数组，其中项目都不会重复或重复。

由于我们不需要实际的总数，我们可以进一步简化这一点，只考虑parity。这是一个返工，它使用并使用这个问题不断发展的新规则，寻找奇怪的人：

public int solution(int[] a) {

    Map<Integer, Boolean> odd = new HashMap<>();

    for (int key : a) {

        odd.put(key, (odd.containsKey(key)) ? ! odd.get(key) : Boolean.TRUE);

    }

    for (Map.Entry<Integer, Boolean> entry : odd.entrySet()) {

        if (entry.getValue()) {

            return entry.getKey();

        }

    }

    return 0;

}

我们现在知道，失败时返回零：

A 是 [1..1,000,000,000] 范围内的整数

Answer 3

一种方法是创建一个包含每个值的频率的新数组。您可以首先循环遍历初始数组以计算其中的最大值。

例如，数组{9,3,9,3,9,7,7,2,2,11,9}的最大值为 11。使用此信息，创建一个新数组，该数组可以存储初始数组中每个可能值的频率。然后，假设只有一个整数重复一次，返回频率为 1 的新数组的索引。这个方法应该运行在O(n)其中 n 是输入数组的大小。

这是一个实现：

public int solution(int[] inp)

{

    int max = inp[0];

    for(int i = 1; i < inp.length; i++)

    {

        if(inp[i] > max)

            max = inp[i];

    }

    int[] histogram = new int[max + 1]; //We add 1 so we have an index for our max value

    for(int i = 0; i < inp.length; i++)

        histogram[inp[i]]++; //Update the frequency

    for(int i = 0; i < histogram.length; i++)

    {

        if(histogram[i] == 1)

            return i;

    }

    return -1; //Hopefully this doesn't happen

}

希望这可以帮助