9

O(logn) で行わなければならない面接の質問に出くわしました

ソートされた整数配列と数値を指定して、配列内の数値の開始インデックスと終了インデックスを見つけます。

Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6} 

Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}

私はこれのための効率的なアルゴリズムを見つけようとしていますが、脂肪は成功していません.

4

6 に答える 6

2

解決策は、最初に配列を同時にバイナリ検索することです（実際には並行である必要はありません:P）。重要なのは、左右の検索がわずかに異なることです。デュープに遭遇した場合は右側を検索する必要があり、デュープに遭遇した場合は左側を検索する必要があります。あなたが探しているのは境界なので、右側でチェックします。 

 yournum, not_yournum

これが境界で、左側では境界を反対方向に検索します。最後に、境界のインデックスを返します。

于 2013-11-07T18:48:31.843 に答える
2

二分探索のように聞こえます。ログ グラフ iirc は、増分ごとに「半分にする」効果を表します。これは基本的に二分探索です。

擬似コード:

Set number to search for
Get length of array, check if number is at the half point
if the half is > the #, check the half of the bottom half. is <, do the inverse
repeat
    if the half point is the #, mark the first time this happens as a variable storing its index
    then repeat binary searches above , and then binary searches below (separately), such that you check for how far to the left/right it can repeat.
    note*: and you sort binary left/right instead of just incrementally, in case your code is tested in a dataset with like 1,000,000 3's in a row or something

これはそこから行くのに十分明確ですか？

于 2013-11-07T18:41:03.563 に答える
0

二重二分探索。下限インデックス = 0、上限インデックス = 長さ - 1 から開始します。次に、ポイントを途中で確認し、それに応じてインデックスを調整します。

トリックは、ターゲットを見つけたら、ピボットが 2 つのピボットに分割されることです。

于 2013-11-07T18:42:49.893 に答える
0

まだ誰も動作コードを投稿していないので、いくつか投稿します (Java):

public class DuplicateNumberRangeFinder {
    public static void main(String[] args) {
        int[] nums = { 0, 0, 2, 3, 3, 3, 3, 4, 7, 7, 9 };
        Range range = findDuplicateNumberRange(nums, 3);

        System.out.println(range);
    }

    public static Range findDuplicateNumberRange(int[] nums, int toFind) {
        Range notFound = new Range(-1, -1);

        if (nums == null || nums.length == 0) {
            return notFound;
        }

        int startIndex = notFound.startIndex;
        int endIndex = notFound.endIndex;
        int n = nums.length;
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] == toFind && (mid == 0 || nums[mid - 1] < toFind)) {
                startIndex = mid;
                break;
            } else if (nums[mid] < toFind) {
                low = mid + 1;
            } else if (nums[mid] >= toFind) {
                high = mid - 1;
            }
        }

        low = 0;
        high = n - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] == toFind && (mid == n - 1 || nums[mid + 1] > toFind)) {
                endIndex = mid;
                break;
            } else if (nums[mid] <= toFind) {
                low = mid + 1;
            } else if (nums[mid] > toFind) {
                high = mid - 1;
            }
        }

        return new Range(startIndex, endIndex);
    }

    private static class Range {
        int startIndex;
        int endIndex;

        public Range(int startIndex, int endIndex) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        public String toString() {
            return "[" + this.startIndex + ", " + this.endIndex + "]";
        }
    }
}
于 2014-11-07T05:38:22.303 に答える