使用二进制搜索来查找数字数组中出现奇数次的数字

Question

我可以在第一个示例中做到这一点，但例如，我无法获得正确的答案。我的代码实际上寻找中间位置，并将数组遍历到数组的右侧，因为mid -1 = mid，这使条件成立，但是mid -1 = mid -2。我应该怎么做才能忽略这一点？

 import java.util.Arrays;

class Lab4 {
// Function to return k'th smallest
// element in a given array


public static int findOddNumber(int[] numbers, int startIndex, int endIndex) {

    int mid = 0;
    mid = (startIndex + endIndex) / 2;

    if (startIndex == endIndex) {
        return numbers[startIndex];
    }
    if (mid % 2 == 0) {
        if (numbers[mid] == numbers[mid + 1]) {
            return findOddNumber(numbers, mid + 2, endIndex);
        } else {
            return findOddNumber(numbers, startIndex, mid);
        }
    } else {
        if (numbers[mid] == numbers[mid - 1])
            return findOddNumber(numbers, mid + 1, endIndex);
        else
            return findOddNumber(numbers, startIndex, mid - 1);
    }
}

// driver program
public static void main(String[] args) {


    int arr2[] = new int[] { 1, 1, 2, 3, 3, 5, 5 };
    System.out.println("Odd number is " + findOddNumber(arr2, 0, arr2.length - 1));

    int arr3[] = new int[] { 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6 };
    System.out.println("Odd number is " + findOddNumber(arr3, 0, arr3.length-1));

    }

}

Answer 1

抱歉，我现在了解您的解决方案。问题之一是，仅通过查看中点左右的元素，您仍然不知道该走哪条路。因此，这是一个适应方法：使用二进制搜索找到与中值相同的最后一个索引。如果是奇数，则必须在该索引的右侧子数组中搜索，否则必须在左侧查找。时间复杂度为O（（logn）^ 2），但仅适用于有一个元素出现奇数次的有序数组。在代码中：

public static int findOddNumber(int[] numbers, int startIndex, int endIndex) {
    if (numbers[startIndex] == numbers[endIndex])
        return numbers[startIndex];
    int mid = (startIndex + endIndex) / 2;
    int last = findLast(numbers, mid, endIndex);
    if (last % 2 == 1)
        return findOddNumber(numbers, last + 1, endIndex);
    else
        return findOddNumber(numbers, startIndex, mid - mid % 2);
}

private static int findLast(int[] numbers, int startIndex, int endIndex) {
    if (numbers[startIndex] == numbers[endIndex])
        return endIndex;
    int mid = (startIndex + endIndex) / 2;
    if (numbers[startIndex] == numbers[mid])
        return findLast(numbers, mid, endIndex - 1);
    else
        return findLast(numbers, startIndex, mid - 1);
}

---

对于无序数组，可以使用散列集找到所有奇数的更简单方法。这也适用于多个奇数。只需遍历数组，如果数字已经在集合中，请将其删除，否则将其添加。最后，所有数字在哈希集中都显示为奇数次。这需要O（n）的时间和空间。

如果知道只有一个数字出现奇数次，则可以对所有数组值进行异或运算并获得解决方案。 O（n）时间和O（1）空间。这也适用于无序数组。

Answer 2

假设它是一个排序的数组，您可以获得的最佳“最坏情况下的时间复杂度”是O（n）。之所以如此，是因为最坏的情况是数组中的所有元素都不同并且每个元素仅出现一次。（例如-> 1,2,3,4,5）

O（n）时间复杂度和O（1）空间复杂度的解决方案是使用curr_element（存储可能重复的curr_element），一个计数变量（以计算curr_element的出现次数）和一个数组进行迭代。总变量（问题的答案）额外。迭代，计算curr_element的出现次数，如果为奇数，则累加总数。

在这种情况下，没有比O（n）更好的解决方案。

Answer 3

可以通过子范围的长度进行二进制搜索。

必须确保子范围来自划分范围，使得第二个子范围以不同的值开头，而第一个以。结尾

您的解决方案未循环进行拆分。同样，必须检查子范围length

的奇数，而不是mid索引。

public static int findOddNumber(int[] numbers) {
    return findOddNumber(numbers, 0, numbers.length);
}
使用递归二进制分割：

/**
 * @param numbers where only one value occurs an odd number of times.
 * @param startIndex.
 * @param endIndex exclusive.
 */
public static int findOddNumber(int[] numbers, int startIndex, int endIndex) {
    assert endIndex - startIndex % 2 == 1;

    if (endIndex - startIndex == 1) {
        return numbers[startIndex];
    }
    // Now at least two elements.

    // Try to split into two subranges, the first ending with a different value
    // as the second subrange.
    int mid = (startIndex + endIndex) / 2;

    // Do not split inside subrange of the same number:
    int split = mid + 1;
    while (split < endIndex && numbers[split] == numbers[split - 1]) {
        ++split;
    }
    if (split == endIndex) {
        split = mid;
        while (split > startIndex && numbers[split] == numbers[split - 1]) {
            --split;
        }
    }
    if (split == startIndex || split == endIndex) { // Could not split.
        return numbers[startIndex]; // All numbers the same.
    }
    if ((split - startIndex) % 2 == 1) {
        return findOddNumberIndex(numbers, startIndex, split);
    } else {
        return findOddNumberIndex(numbers, split, endIndex);
    }
}
现在拆分可以使用二进制搜索（Arrays.binarySearch）通过搜索数字[mid] +或-0.5来查找开始和结束，但这在这里不可行。

---

出于好奇，当不对数字进行排序时，这是一种替代解决方案：

public static int findOddNumber(int[] numbers) {
    int result = 0;
    for (int n : numbers) {
        retult ^= n;
    }
    return n;
}
这利用x ^ x == 0和0 ^ x == x。 ^（XOR）是可交换的和关联的。