LeetCode #35 Cover Photo - searching

LeetCode #35 Search Insert Position  尋找陣列中插入的位置

Klook.com
文章觀看次數: 279

英文原文如下

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) 的時間複雜度

範例及題目限制

解題思路

一眼看起來，是不是超級簡單的

筆者就犯了這個錯，直接無視了時間複雜度須為 O(log n) 的這件事

C# 解決方案

給你們看看錯誤的範例，直接用一個迴圈將元素遍歷

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        for(int i=0;i<=nums.Length-1;i++)
        {
            if(target<=nums[i])
            {
              return i;
            }
        }
        return nums.Length;
    }
}

成功是成功了，但其時間複雜度卻是 O(n)，達不到題目的要求

方案1 – 二分搜尋法（Binary Search）

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } 
            else if (nums[mid] < target) {
                left = mid + 1;
            } 
            else {
                right = mid - 1;
            }
        }

        return left;
    }
}

因為該陣列已經被排序過了，故用二分搜尋法，可以簡單的一次縮減一半的範圍

故擁有極高的效率 (時間複雜度)

Java解決方案

方案1

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } 
            else if (nums[mid] < target) {
                left = mid + 1;
            } 
            else {
                right = mid - 1;
            }
        }

        return left;
    }
}

運行時間 : 0ms、0ms、0ms

Python3 解決方案

方案1

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return left

JavaScript 解決方案

方案1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);

        if (nums[mid] === target) {
            return mid;
        } 
        else if (nums[mid] < target) {
            left = mid + 1;
        } 
        else {
            right = mid - 1;
        }
    }

    return left;
};

結論

這題考到的就是對演算的熟悉程度了，沒學過的話確實不會知道如何降低最初的時間複雜度…

有空的話，專門針對常見的演算法來寫一篇文章好了

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我分享，我都會很感謝的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Search Insert Position – LeetCode

一些隨機文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *