java - 查找排序数组中唯一重复的元素

Question

我知道在排序数组中查找非重复元素的 XOR 技巧(之前已被问过):

public int singleNumber(int[] nums) {
    int result = 0; 
    for (int i = 0; i < nums.length; i++) {
        result = result ^ nums[i]; 
    }
    return result; 
}

但是我们如何使用相同的逻辑来做相反的事情呢？

更具体地说:考虑一个排序数组，其中每个元素仅出现一次，我们如何找到在 O(1) 空间中重复的一个元素？

Answer 1

只有当您想丢弃偶数次重复时，异或技巧才有效。看待它的一种方法是说数组中所有元素的异或就是该数组中奇数重复元素的异或；这样，如果只有一个奇怪重复的元素，您可以通过这种方式找到它。并且您根本不需要对数组进行排序来执行此操作:

// could also have called it xorOfOddlyRepeatingIntsInArray(int[] a)
public static int findSingleNonEvenlyRepetingIntInUnsortedArray(int[] a) {
  int x = 0;
  for (int i: a) x ^= i;
  return x;
}

对于您所要求的，这两个片段都在 O(1) 空间和 O(n) 时间内找到排序数组中的重复元素:

public static int findSingleRepeatingIntInSortedArray1(int[] a) {
  for (int i=0; i<a.length-1; i++) if (a[i] == a[i+1]) return a[i];
  return -1;
}

public static int findSingleRepeatingIntInSortedArray2(int[] a) {
  for (int i=0; i<a.length-1; i++) if ((a[i] ^ a[i+1]) == 0) return a[i];
  return -1;
}

但您应该更喜欢版本 1，因为 a[i] == a[i+1] 比 (a[i] ^ a[i+1]) == 0、或 (a[i] - a[i+1]) == 0、或 (a[i] & a[i+1]) == a[i] 或其他用于检查相等性的神秘变体更具可读性。 在这种情况下，Xor 不会给你带来任何好处。

对于笑声和傻笑，此代码在 未排序 数组中查找 O(1) 空间 中的单个重复值:

 public static int findSingleRepeatingIntInSortedArray3(int[] a) {
    for (int i=0; i<a.length; i++) {
       for (int j=i+1; j<a.length; j++) {
          if (a[i] == a[j]) return a[i];
       }
    }
    return 0;
 }

是的，它是 O(n^2) 时间，并且有更快的方法来查找第一个重复元素(想到排序) - 但这是问题的有效答案。