LeetCode 解答 #35. Search Insert Position プログラミング練習

問題：

難易度:　easy
入力:　int型array、(int)target
目的: ソートされた入力arrayの中で、targetを差し込む場所を求めよ。
出力:　int

入力がArray ->ターゲットを探せ的な問題はまずバイナリサーチを思い浮かべましょう。
♯33、♯34と似た問題です。
入力はソートされており、ターゲットを差し込んだ後も昇順でなければなりません。

注意すべき事:　

• Arrayの中に重複したエレメントは存在しないがtargetと同じ値のエレメントは存在するかもしれない。

• targetと同じ値のエレメントがある場合はその前に差し込む。

• 入力が空の場合も対処する。

以下回答です。

今回は特に時間複雑度に関する要求はないのですが二パターン用意しました。

まずはバイナリサーチ:

class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) return target > nums[0] ? 1 : 0;
        return binarysearch(nums, target, 0, len-1);
    }
    
    public int binarysearch(int[] nums, int target, int start, int end) {
        if (start > end) return start;
        int mid = (start + end) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] > target) return binarysearch(nums, target, start, mid-1);
        else return binarysearch(nums, target, mid+1, end);
    }
}

続けて普通のサーチ:

class Solution {
    public int searchInsert2(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        for (int i=0; i<len; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return len;
    }
}

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

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