更新
有人指出，原始代码需要数组的切片，如果这是通过一个副本来完成的，这会增加复杂性 O(n) . 以下是使用指向数组的指针的代码版本：
java 语：

public static int singleton(int[] arr, int lo, int hi) {
    if (hi == lo) return arr[hi];
    int m = (hi + lo) / 2;        
    if (m % 2 == 1) {
        if (arr[m] == arr[m-1]) return singleton(arr, m+1, hi);
        if (arr[m] != arr[m+1]) return arr[m];
        return singleton(arr, lo, m-1);
    }
    else {
        if (arr[m] == arr[m+1]) return singleton(arr, m+2, hi);
        if (arr[m] != arr[m-1]) return arr[m];
        return singleton(arr, lo, m);
    }
}      
public static void main(String args[])
{
    System.out.println(singleton(new int[]{ 1,1,2,2,4,5,5 }, 0, 6));
    System.out.println(singleton(new int[]{ 10,10,12,12,15,15,16,18,18 }, 0, 8));
    System.out.println(singleton(new int[]{1,2,2,5,5,6,6,7,7}, 0, 8));
    System.out.println(singleton(new int[]{1,1,2,5,5,6,6,7,7}, 0, 8));
    System.out.println(singleton(new int[]{10,10,12,12,15,15,16,16,18}, 0, 8));
}

Python：

def singleton(arr, lo, hi):
    if (hi == lo):
        return arr[hi]
    m = (hi + lo) // 2
    if (m % 2 == 1):
        if (arr[m] == arr[m-1]):
            return singleton(arr, m+1, hi)
        if (arr[m] != arr[m+1]):
            return arr[m]
        return singleton(arr, lo, m-1);
    else:
        if (arr[m] == arr[m+1]):
            return singleton(arr, m+2, hi)
        if (arr[m] != arr[m-1]):
            return arr[m]
        return singleton(arr, lo, m);

原始答案
因为您知道数组中的所有其他整数正好出现两次，所以可以执行二进制搜索来查找只出现一次的值。您需要查找数组的中点，并确定单例是出现在该数字之前、之后还是该数字。如果是在之前或之后，则继续搜索，但只搜索数组的该部分（最多一半）。这是 O(logn) . 在python中（注意：当我最初回答这个问题时，它没有被标记为 java -我随后在下面添加了一个java解决方案）您可以将其实现为：

def singleton(arr):
    m = len(arr) // 2
    if (m == 0):
        return arr[0]
    if m % 2 == 1:
        if arr[m] == arr[m-1]:
            return singleton(arr[m+1:])
        if arr[m] != arr[m+1]:
            return arr[m]
        return singleton(arr[:m])
    else:
        if arr[m] == arr[m+1]:
            return singleton(arr[m+2:])
        if arr[m] != arr[m-1]:
            return arr[m]
        return singleton(arr[:m+1])

示例用法：

print(singleton([1,1,2,2,4,5,5]))
print(singleton([10,10,12,12,15,15,16,18,18]))
print(singleton([1,2,2,5,5,6,6,7,7]))
print(singleton([1,1,2,5,5,6,6,7,7]))
print(singleton([10,10,12,12,15,15,16,16,18]))

输出：

4
16
1
2
18

我不是javaMaven，所以这可能不是最有效的方法，但确实有效：

public static int singleton(int[] arr) {
    int m = arr.length / 2;
    if (m == 0) return arr[0];
    if (m % 2 == 1) {
        if (arr[m] == arr[m-1]) return singleton(Arrays.copyOfRange(arr, m+1, arr.length));
        if (arr[m] != arr[m+1]) return arr[m];
        return singleton(Arrays.copyOfRange(arr, 0, m));
    }
    else {
        if (arr[m] == arr[m+1]) return singleton(Arrays.copyOfRange(arr, m+2, arr.length));
        if (arr[m] != arr[m-1]) return arr[m];
        return singleton(Arrays.copyOfRange(arr, 0, m+1));
    }
}      
public static void main(String args[])
{
    System.out.println(singleton(new int[]{ 1,1,2,2,4,5,5 }));
    System.out.println(singleton(new int[]{ 10,10,12,12,15,15,16,18,18 }));
    System.out.println(singleton(new int[]{1,2,2,5,5,6,6,7,7}));
    System.out.println(singleton(new int[]{1,1,2,5,5,6,6,7,7}));
    System.out.println(singleton(new int[]{10,10,12,12,15,15,16,16,18}));
}