9

数字の連続リストで重複を見つけるための線形よりも速いアルゴリズムを知っている人はいますか？私は現在Javaで作業していますが、どの言語や疑似コードでも問題ありません。

たとえば、次のint[]入力が与えられます。

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 7 | 8 | 9

出力は、インデックスまたは値「7」のいずれかになります。

線形時間での明らかな走査を知っていますO(n)が、これが時間での二分探索によって可能かどうかを確認しようとしてO(log n)います。

4

3 に答える 3

14

数値が0から始まり、1ずつ増加する必要があると想定する場合は、中央をインデックスと比較できます。真ん中が同じ場合は高くし、真ん中が同じでない場合は低くします。

これにより、バイナリ検索時間O（log2 N）が得られます。唯一の違いは、固定値ではなく、インデックスと比較していることです。

public static void main(String... args) {
    int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9};
    int duplicate = findDuplicate(array);
    System.out.println(duplicate);
}

private static int findDuplicate(int[] array) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = array[mid];

        if (midVal == mid)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return high;
}
于 2012-09-11T14:48:35.403 に答える
1

バイナリ検索は、ソートされたリストで機能することを目的としていることに注意してください。したがって、重複のあるソート済みリストがある場合、バイナリ検索は重複が隣接している場合にのみ役立ちます。隣接していることの重要性は、見つかったキーの前後の位置でキーの存在をテストできるようにすることです。ソートされていないリストでバイナリ検索を使用しようとする他の方法では、誤った結果が得られます。

これが私が何を意味するかを示すための少しのコードです。

import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        int[] list = {1, 2, 3, 4, 5, 6, 7, 7, 8, 9 };
        int key = 7;
        int result = Arrays.binarySearch(list, key);
        System.out.println(result);
        if( list[result+1] == key  || list[result-1] == key )
                System.out.println("yes we have a duplicate.");
    }
}

O（1）であることの比較は、if二分探索のO（logn）と残っています。

于 2012-09-11T15:13:44.593 に答える
1 
public class DuplicateNumber {

    public int findDuplicateNumber(List<Integer> numbers){

        int highestNumber = numbers.size() - 1;
        int total = getSum(numbers);
        int duplicate = total - (highestNumber*(highestNumber+1)/2);
        return duplicate;
    }

    public int getSum(List<Integer> numbers){

        int sum = 0;
        for(int num:numbers){
            sum += num;
        }
        return sum;
    }

    public static void main(String a[]){
        List<Integer> numbers = new ArrayList<Integer>();
        for(int i=1;i<30;i++){
            numbers.add(i);
        }
        //add duplicate number into the list
        numbers.add(22);
        DuplicateNumber dn = new DuplicateNumber();
        System.out.println("Duplicate Number: "+dn.findDuplicateNumber(numbers));
    }
}
于 2013-09-07T10:32:03.267 に答える