arrays - 在0和1的排序数组中找到1的位置的解决方案

Question

我接到亚马逊的电话参加他们的一次面试，并进行了测试，以编写最有效的解决以下问题的方法。

要在 0 和 1 的排序数组中找到 1 的最小位置。例如，在数组 0000001111 中，输出应为 6。

我对此进行了 binary_search 尝试，但它没有利用数组只有 0 和 1 的属性。你能给我一些更好的解决方案吗？

谢谢尼拉吉·拉蒂

Answer 1

您可以使用值为 0 和 1 的事实以更紧凑的方式编写标准二进制搜索：

int firstOne(int[] arr) {
    int[] a = new int[2];
    a[0] = 0;
    a[1] = arr.length;

    while (a[1] - a[0] > 1) {
        int m = (a[1] + a[0]) / 2;
        a[arr[m]] = m;
    }

    return a[1];
}

由于使用了数组a，我们有不变量 thatarr[a[0]] = 0和arr[a[1]] = 1。如果循环结束，a[0]并a[1]指向两个连续的数组元素，那么a[1]第一个 1 也是如此。请注意，我忽略了特殊情况（全 0、全 1 或空输入）。

Answer 2

和二进制一样试试这个..

while
{
   if array[array.length/2] == 1
   {
        if array[array.length/2 - 1 ] == 0
             return
        array = 1st half of array
   }
   else
   {
       if array[array.length/2 + 1 ] == 0
             return
       array = 2nd half of array
   }
}

可能是您在寻找如果有比这更好的想法我真的很想学习