LeetCode 解答 #34. Search for a Range プログラミング練習

問題：

難易度:　medium
入力:　int型array、(int)target
目的: 入力されたarrayの中で、targetの値と一致するエレメントの始まりと終わりのindexを求めよ
出力:　int型Array

前の♯33問目と殆ど同じ内容です。
更に今回はRotateされていないので、昇順にソートされています。
但し、今回は重複したノードが存在するのでエレメントの範囲を求めることになります。

注意すべき事:　

• 一致するエレメントがない場合は[-1, -1]を返す

• 時間複雑度はO(logn)に抑えるべき。

以下回答です。
O(logn)に抑えろとの事なのでバイナリサーチを使うべき。
簡単なので普通のO(n)の方法も作りました。

まずはバイナリサーチ:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) return new int[]{-1,-1};
        if (nums.length == 1 && nums[0] == target) return new int[]{0,0};
        return binarysearch(nums, target, 0, nums.length - 1);
    }
    
    public int[] binarysearch(int[] nums, int target, int start, int end) {
        if (start > end) {
            int[] res = new int[]{-1, -1};
            return res;
        }
        int mid = (start + end) / 2;
        if (nums[mid] == target) {
            int left = 0, right = 0;
            while (mid - left >= 0 && nums[mid-left] == target) left++;
            while (mid + right < nums.length && nums[mid+right] == target) right++;
            int[] res = new int[]{mid-left+1, mid+right-1};
            return res;
        }
        if (nums[mid] > target) {
            return binarysearch(nums, target, start, mid-1);
        } else {
            return binarysearch(nums, target, mid+1, end);
        }
    }
}

続けて普通のサーチ:

class Solution {
    public int[] searchRange2(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        for (int i=0; i<nums.length; i++) {
            if (nums[i] == target) {
                int j = i+1;
                while ( j<nums.length && nums[j] == target ) j++;
                res[0] = i;
                res[1] = j-1;
                return res;
            }
        }
        return res;
    }
}

バイナリサーチのワーストケースはO(logn)で二番目の方法のワーストケースはO(n)です。
結果はバイナリサーチが7ms、全体サーチが8msでした。
問題としてはソートされたArrayなのでどちらも標準アルゴリズムを少し変えた程度です。

今日は以上。
よいプログラミング生活を！