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

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

@Test

public void test(){

    OddOccurance oddOccurance =new OddOccurance();

    int odd=oddOccurance.solution(A);

    assertEquals(7,odd);

}

@Test

public void test2(){

    OddOccurance oddOccurance =new OddOccurance();

    int odd=oddOccurance.solution(A2);

    assertEquals(3,odd);

}

@Test

public 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, 21 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) {&nbsp; &nbsp; Integer ONE = 1;&nbsp; &nbsp; Map<Integer, Integer> map = new HashMap<>();&nbsp; &nbsp; for (int key : a) {&nbsp; &nbsp; &nbsp; &nbsp; Integer value = (map.containsKey(key)) ? map.get(key) + ONE : ONE;&nbsp; &nbsp; &nbsp; &nbsp; map.put(key, value);&nbsp; &nbsp; }&nbsp; &nbsp; for (Map.Entry<Integer, Integer> entry : map.entrySet()) {&nbsp; &nbsp; &nbsp; &nbsp; if (entry.getValue().equals(ONE)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return entry.getKey();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return -1;}我假设奇数数组长度要求是为了避免长度为 2 的数组，其中项目都不会重复或重复。由于我们不需要实际的总数，我们可以进一步简化这一点，只考虑parity。这是一个返工，它使用并使用这个问题不断发展的新规则，寻找奇怪的人：public int solution(int[] a) {&nbsp; &nbsp; Map<Integer, Boolean> odd = new HashMap<>();&nbsp; &nbsp; for (int key : a) {&nbsp; &nbsp; &nbsp; &nbsp; odd.put(key, (odd.containsKey(key)) ? ! odd.get(key) : Boolean.TRUE);&nbsp; &nbsp; }&nbsp; &nbsp; for (Map.Entry<Integer, Boolean> entry : odd.entrySet()) {&nbsp; &nbsp; &nbsp; &nbsp; if (entry.getValue()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return entry.getKey();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; 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){&nbsp; &nbsp; int max = inp[0];&nbsp; &nbsp; for(int i = 1; i < inp.length; i++)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(inp[i] > max)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; max = inp[i];&nbsp; &nbsp; }&nbsp; &nbsp; int[] histogram = new int[max + 1]; //We add 1 so we have an index for our max value&nbsp; &nbsp; for(int i = 0; i < inp.length; i++)&nbsp; &nbsp; &nbsp; &nbsp; histogram[inp[i]]++; //Update the frequency&nbsp; &nbsp; for(int i = 0; i < histogram.length; i++)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(histogram[i] == 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i;&nbsp; &nbsp; }&nbsp; &nbsp; return -1; //Hopefully this doesn't happen}希望这可以帮助