27

ソートされた配列で値xが見つかったすべてのインデックスを出力するメソッドを作成する必要があります。

アレイを0からN（アレイの長さ）までスキャンした場合、実行時間は最悪の場合O（n）になることを理解しています。メソッドに渡される配列がソートされるので、これはO（log n）になるので、二分探索を利用できると思います。ただし、これは、配列に一意の値がある場合にのみ機能します。バイナリ検索は、特定の値の最初の「検索」の後に終了するためです。ソートされた配列でxを見つけるために二分探索を実行し、このインデックスの前後のすべての値をチェックすることを考えていましたが、配列にすべてのx値が含まれている場合、それほど良いとは思えません。

私が求めているのは、O（n）よりも優れているソートされた配列内の特定の値のすべてのインデックスを見つけるためのより良い方法があると思いますか？

public void PrintIndicesForValue42(int[] sortedArrayOfInts)
{
    // search through the sortedArrayOfInts

    // print all indices where we find the number 42. 
}

例：sortedArray = {1、13、42、42、42、77、78}は次のように出力します：「42はインデックスで見つかりました：2、3、4」

4

10 に答える 10

40

結果はO（lg n）になります

public static void PrintIndicesForValue(int[] numbers, int target) {
    if (numbers == null)
        return;

    int low = 0, high = numbers.length - 1;
    // get the start index of target number
    int startIndex = -1;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        if (numbers[mid] > target) {
            high = mid - 1;
        } else if (numbers[mid] == target) {
            startIndex = mid;
            high = mid - 1;
        } else
            low = mid + 1;
    }

    // get the end index of target number
    int endIndex = -1;
    low = 0;
    high = numbers.length - 1;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        if (numbers[mid] > target) {
            high = mid - 1;
        } else if (numbers[mid] == target) {
            endIndex = mid;
            low = mid + 1;
        } else
            low = mid + 1;
    }

    if (startIndex != -1 && endIndex != -1){
        for(int i=0; i+startIndex<=endIndex;i++){
            if(i>0)
                System.out.print(',');
            System.out.print(i+startIndex);
        }
    }
}
于 2013-12-03T18:01:45.943 に答える
23

さて、実際にソートされた配列がある場合は、探しているインデックスの1つが見つかるまでバイナリ検索を実行できます。そこから、残りはすべてそれぞれの隣にあるため、簡単に見つけることができます。他の。

最初のインスタンスを見つけたら、その前のすべてのインスタンスを見つけてから、その後のすべてのインスタンスを見つけます。

このメソッドを使用すると、おおよそO（lg（n）+ k）が得られます。ここで、 kは検索している値の出現回数です。

編集：

そして、いいえ、 O（k）時間 未満ですべてのk値にアクセスすることはできません。


2番目の編集：私が実際に何か有用なものに貢献しているように感じることができるように：

Xの最初と最後のオカレンスを検索する代わりに、最初のオカレンスのバイナリ検索と最後のオカレンスのバイナリ検索を実行できます。これにより、合計はO（lg（n））になります。これを実行すると、インデックス間のすべてのインデックスにもXが含まれていることがわかります（ソートされていると仮定します）

これを行うには、値がxに等しいかどうかを検索し、左側（または最初の出現または最後の出現を探しているかどうかによっては右側）の値がxに等しいかどうかをチェックします。

于 2012-11-02T14:52:19.413 に答える
3 
public void PrintIndicesForValue42(int[] sortedArrayOfInts) {
    int index_occurrence_of_42 = left = right = binarySearch(sortedArrayOfInts, 42);
    while (left - 1 >= 0) {
        if (sortedArrayOfInts[left-1] == 42)
            left--;
    }
    while (right + 1 < sortedArrayOfInts.length) {
        if (sortedArrayOfInts[right+1] == 42)
            right++;
    }
    System.out.println("Indices are from: " + left + " to " + right);
}

これはO（log（n）+ #occurrences）で実行されます。コードを読んで理解します。とても簡単です。

于 2012-11-02T15:46:45.547 に答える
2

私は二分探索を使用して解決策を思いつきました、唯一のことは一致が見つかった場合に両側で二分探索を行うことです。

public static void main(String[] args) {
    int a[] ={1,2,2,5,5,6,8,9,10};
    System.out.println(2+" IS AVAILABLE  AT = "+findDuplicateOfN(a, 0, a.length-1, 2));
    System.out.println(5+" IS AVAILABLE  AT = "+findDuplicateOfN(a, 0, a.length-1, 5));
    int a1[] ={2,2,2,2,2,2,2,2,2};
    System.out.println(2+" IS AVAILABLE  AT = "+findDuplicateOfN(a1, 0, a1.length-1, 2));

    int a2[] ={1,2,3,4,5,6,7,8,9};
    System.out.println(10+" IS AVAILABLE  AT = "+findDuplicateOfN(a2, 0, a2.length-1, 10));
}

public static String findDuplicateOfN(int[] a, int l, int h, int x){
    if(l>h){
        return "";
    }
    int m = (h-l)/2+l;
    if(a[m] == x){
        String matchedIndexs = ""+m;
        matchedIndexs = matchedIndexs+findDuplicateOfN(a, l, m-1, x);
        matchedIndexs = matchedIndexs+findDuplicateOfN(a, m+1, h, x);
        return matchedIndexs;
    }else if(a[m]>x){
        return findDuplicateOfN(a, l, m-1, x);
    }else{
        return findDuplicateOfN(a, m+1, h, x);
    }
}


2 IS AVAILABLE  AT = 12 
5 IS AVAILABLE  AT = 43 
2 IS AVAILABLE  AT = 410236578 
10 IS AVAILABLE  AT =

これはまだO（logn）の複雑さの結果を提供していると思います。

于 2017-12-07T05:20:00.790 に答える
1

バイナリ検索を使用する必要がない場合は、ハッシュマップが機能する可能性があります。

が値自体であるHashMapを作成し、Keyvalueがインデックスの配列であり、その値が配列内にある場合。配列をループし、値ごとにHashMapの各配列を更新します。

各値のインデックスのルックアップ時間は〜O（1）になり、マップ自体の作成は〜O（n）になります。

于 2012-11-02T14:53:27.720 に答える
1 
Find_Key(int arr[], int size, int key){
int begin = 0;
int end = size - 1;
int mid = end / 2;
int res = INT_MIN;

while (begin != mid)
{
    if (arr[mid] < key)
        begin = mid;
    else
    {
        end = mid;
        if(arr[mid] == key)
            res = mid;
    }
    mid = (end + begin )/2;
}
return res;
}

intの配列が昇順でソートされていると仮定します。キーオカレンスの最初のインデックスまたはINT_MINのインデックスを返します。O（lg n）で実行されます。

于 2014-02-06T00:44:47.010 に答える
1

以下は、指定されたソート済み配列で検索キーが分散される範囲を返すJavaコードです。

public static int doBinarySearchRec(int[] array, int start, int end, int n) {
    if (start > end) {
        return -1;
    }
    int mid = start + (end - start) / 2;

    if (n == array[mid]) {
        return mid;
    } else if (n < array[mid]) {
        return doBinarySearchRec(array, start, mid - 1, n);
    } else {
        return doBinarySearchRec(array, mid + 1, end, n);
    }
}

/**
 * Given a sorted array with duplicates and a number, find the range in the
 * form of (startIndex, endIndex) of that number. For example,
 * 
 * find_range({0 2 3 3 3 10 10}, 3) should return (2,4). find_range({0 2 3 3
 * 3 10 10}, 6) should return (-1,-1). The array and the number of
 * duplicates can be large.
 * 
 */
public static int[] binarySearchArrayWithDup(int[] array, int n) {

    if (null == array) {
        return null;
    }
    int firstMatch = doBinarySearchRec(array, 0, array.length - 1, n);
    int[] resultArray = { -1, -1 };
    if (firstMatch == -1) {
        return resultArray;
    }
    int leftMost = firstMatch;
    int rightMost = firstMatch;

    for (int result = doBinarySearchRec(array, 0, leftMost - 1, n); result != -1;) {
        leftMost = result;
        result = doBinarySearchRec(array, 0, leftMost - 1, n);
    }

    for (int result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n); result != -1;) {
        rightMost = result;
        result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n);
    }

    resultArray[0] = leftMost;
    resultArray[1] = rightMost;

    return resultArray;
}
于 2014-11-02T18:54:56.657 に答える
1

修正二分探索を使用しています。O（LogN）になります。スペースの複雑さはO（1）になります。BinarySearchModifiedを2回呼び出しています。1つは要素の開始インデックスを検索するためのもので、もう1つは要素の終了インデックスを検索するためのものです。

private static int BinarySearchModified(int[] input, double toSearch)
    {
        int start = 0;
        int end = input.Length - 1;

        while (start <= end)
        {
            int mid = start + (end - start)/2;
            if (toSearch < input[mid]) end = mid - 1;
            else start = mid + 1;
        }

        return start;
    }


    public static Result GetRange(int[] input, int toSearch)
    {
        if (input == null) return new Result(-1, -1);

        int low = BinarySearchModified(input, toSearch - 0.5);

        if ((low >= input.Length) || (input[low] != toSearch)) return new Result(-1, -1);

        int high = BinarySearchModified(input, toSearch + 0.5);

        return new Result(low, high - 1);
    } 

 public struct Result
    {
        public int LowIndex;
        public int HighIndex;

        public Result(int low, int high)
        {
            LowIndex = low;
            HighIndex = high;
        }
    }
于 2016-01-28T06:18:37.880 に答える
1

左端のターゲットと右端のターゲットのlog（n）バイナリ検索の別の結果。これはC++ですが、かなり読みやすいと思います。

アイデアは、私たちが常にいつ終わるかということleft = right + 1です。したがって、左端のターゲットを見つけるために、rightターゲットよりも小さい右端の数に移動できる場合、左が左端のターゲットになります。

左端のターゲットの場合：

int binary_search(vector<int>& nums, int target){
    int n = nums.size();
    int left = 0, right = n - 1;

    // carry right to the greatest number which is less than target.
    while(left <= right){
        int mid = (left + right) / 2;
        if(nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    // when we are here, right is at the index of greatest number
    // which is less than target and since left is at the next, 
    // it is at the first target's index
    return left;
}

右端のターゲットの場合、考え方は非常に似ています。

int binary_search(vector<int>& nums, int target){
    while(left <= right){
        int mid = (left + right) / 2;
        // carry left to the smallest number which is greater than target.
        if(nums[mid] <= target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    // when we are here, left is at the index of smallest number
    // which is greater than target and since right is at the next, 
    // it is at the first target's index
    return right;
}
于 2017-10-26T08:52:54.663 に答える
0 
public void printCopies(int[] array)
{
    HashMap<Integer, Integer> memberMap = new HashMap<Integer, Integer>();
    for(int i = 0; i < array.size; i++)
       if(!memberMap.contains(array[i]))
           memberMap.put(array[i], 1);
       else
       {
           int temp = memberMap.get(array[i]); //get the number of occurances
           memberMap.put(array[i], ++temp); //increment his occurance
       }

    //check keys which occured more than once
    //dump them in a ArrayList
    //return this ArrayList
 }

または、発生数をカウントする代わりに、インデックスを配列リストに入れて、カウントの代わりにマップに入れることができます。

   HashMap<Integer, ArrayList<Integer>> 
   //the integer is the value, the arraylist a list of their indices

public void printCopies(int[] array)
{
    HashMap<Integer, ArrayList<Integer>> memberMap = new HashMap<Integer, ArrayList<Integer>>();
    for(int i = 0; i < array.size; i++)
       if(!memberMap.contains(array[i]))
       {
           ArrayList temp = new ArrayList();
           temp.add(i);
           memberMap.put(array[i], temp);
       }
       else
       {
           ArrayList temp = memberMap.get(array[i]); //get the lsit of indices
           temp.add(i);
           memberMap.put(array[i], temp); //update the index list
       }

    //check keys which return lists with length > 1
    //handle the result any way you want
 }

ええ、これは投稿する必要があると思います。

 int predefinedDuplicate = //value here;
 int index = Arrays.binarySearch(array, predefinedDuplicate);
 int leftIndex, rightIndex;
 //search left
 for(leftIndex = index; array[leftIndex] == array[index]; leftIndex--); //let it run thru it
 //leftIndex is now the first different element to the left of this duplicate number string
 for(rightIndex = index; array[rightIndex] == array[index]; rightIndex++); //let it run thru it

 //right index contains the first different element to the right of the string
 //you can arraycopy this [leftIndex+1, rightIndex-1] string or just print it
 for(int i = leftIndex+1; i<rightIndex; i++)
 System.out.println(array[i] + "\t");
于 2012-11-02T14:58:19.447 に答える