Chris's Lab

If you obey all the rules,you miss all the fun.

0%

[LeetCode] 35. Search Insert Position

發表於 分類於 ， ， Disqus：
這題標準運用了二分搜尋法，演算法通常需要使用二分思想，即每次能夠排除一半的範圍，快速的找出陣列中所要求的元素位置

前言

　　這題標準運用了二分搜尋法，演算法通常需要使用二分思想，即每次能夠排除一半的範圍，快速的找出陣列中所要求的元素位置，這樣時間複雜度可達 O(log n)，另外也可以使用一層迴圈找出元素位置，但時間複雜度會下修到O(n)，這裡有 JAVA 和 Python 的寫法。

題目

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.

給定一個已排序過有不同整數和目標值的陣列，如果有這個目標值就回傳這個索引 ，如果沒有這個值，就回傳按順序插入後的索引。
你必須寫出一個算法，為 O(log n) 的時間複雜度。

題目連結：https://leetcode.com/problems/search-insert-position/

題目限制

1 <= nums.length <= 104
104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
104 <= target <= 104

範例

1
2
Input: nums = [1,3,5,6], target = 5
Output: 2
1
2
Input: nums = [1,3,5,6], target = 2
Output: 1
1
2
Input: nums = [1,3,5,6], target = 7
Output: 4

思路&筆記

主要是運用二分搜尋法來快速的找到值的位置，原理是每次循環都會將搜索範圍縮小一半。
如果 target 比中間值大，那麼搜索範圍將在中間值的右側。
如果 target 比中間值小，那麼搜索範圍將在中間值的左側。

  1. middle = start + ( end - start ) / 2 可取得中間值
  2. 找出目標值在中間值的左側還是右側
  3. 搜索範圍越來越小，直到最後回傳起點位置就是答案

[注意點] 之所以要用上述中間值的寫法會比較安全，因如果 start 和 end 趨近於最大數時，兩者相加起來的合可能會造成整數溢位

[備註] 回傳 start 原因是，在二分搜尋法中，每次都會將搜索範圍縮小一半。而搜尋範圍最小的時候，如果目標值不在該範圍內，那麼搜尋將停止。而此時，start 和 end 分別會指向搜尋範圍的左右兩端，此時 start 恰好會指向 target 應該插入的位置，因此最後返回 start 即可。

JAVA 實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int searchInsert(int[] nums, int target) {

        int start = 0; // 起點位置
        int end = nums.length-1; // 終點位置

        // 進入迴圈
        while (start <= end ){

            // 創建中間值
            int middle = start + ( end - start ) / 2;

            if (target == nums[middle]) { // 目標值 = 陣列中間值
                return middle; // 找到答案，回傳中間值索引

            }else if (target < nums[middle]) { // 目標值 < 陣列中間值 
                end = middle-1; // 重新定義終點，下次回圈找到新的終點就好 (因為目標值一定比自己小，要不包含 middle 自己)

            }else { // 目標值 > 陣列中間值 
                start = middle+1; // 重新定義起點，下次回圈從新的起點開始就好 (因為目標值一定比自己大，要不包含 middle 自己)
            }
        }
        return start;
    }
}

JAVA 其他實現

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int searchInsert(int[] nums, int target) {

        int len = nums.length; // 陣列長度
        
        for (int i = 0; i < len; i++) {
            if (nums[i] >= target) { // 大於等於目標值
                return i; // 就回傳當前索引
            }
        }
        return len;
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:

        start = 0 # 起點

        end = len(nums)-1 # 終點

        while start <= end:

            # 設定中間值
            middle = start + (end-start)//2	

            # 判斷 target 是否等於 middle
            if target == nums[middle]:
                return middle

            # 判斷 target 是否大於
            elif target > nums[middle]:
                start = middle+1

            # 判斷 target 是否小於
            else :
                end = middle-1
        return start

成績

Language Runtime Memory
Java 0ms 41.9MB
Python 63ms 17.2MB