0

Amazonからインタビューに参加するよう電話があり、以下の問題に対する最も効率的な解決策を書くためのテストを受けました.

0 と 1 の並べ替えられた配列で 1 の最小位置を見つけるには、たとえば、配列 0000001111 では、出力は 6 になるはずです。

これで binary_search を試しましたが、配列が 0 と 1 しかないというプロパティを利用していません。より良い解決策を教えてください。

ありがとうニラジ・ラティ

4

2 に答える 2

5

値が 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を使用しているため、 不変式 と がarr[a[0]] = 0ありarr[a[1]] = 1ます。ループが終了し、2 つの連続する配列要素a[0]を指す場合、最初の 1 も同様です。特殊なケース (すべて 0、すべて 1、または空の入力) を無視したことに注意してください。a[1]a[1]

于 2013-09-16T09:56:10.393 に答える
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
   }
}

それはあなたが探しているかもしれません.これよりも優れたアイデアがあれば,私は本当に学びたいと思っています.

于 2013-09-16T07:11:05.897 に答える