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

Question

我可以为我的第一个例子做到这一点，但是对于例子 2，我无法得到正确的答案。我的代码其实就是找中间的位置，遍历数组到数组右边为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

抱歉，我现在明白你的解决方案了。问题之一是，仅通过查看中间右侧或左侧的元素，您仍然无法知道要走哪条路。所以这是一个改编：使用二进制搜索找到与 mid 值相同的最后一个索引。如果是奇数，则必须在该索引右侧的子数组中搜索，否则必须在左侧查找。时间复杂度 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) 时间和 space.

如果你知道恰好有一个数字出现奇数次，那么你可以将所有数组值异或并得到解决方案。 O(n) 时间和 O(1) space。这也适用于无序数组。

Answer 2

假设它是一个排序数组，你能得到的最好的"worst case time complexity"是O(n)。之所以如此，是因为最坏的情况是数组中的所有元素都不同并且每个元素只出现一次。 (例如 -> 1,2,3,4,5)

O(n) 时间复杂度和 O(1) space 复杂度解决方案是使用 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) 具有交换性和结合性。

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

Using binary search for finding the number that appears odd number of times in an array of numbers

java

algorithm

binary-search