LeetCode #34 Find First and Last Position of Element in Sorted Array 已排序陣列中尋找第一次及最後出現的位置

Klook.com
文章觀看次數: 215

英文原文如下

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

中文翻譯

給予一個升幂排序的整數陣列 nums ，尋找一個 target 值在陣列中出現的第一次及最後的位置。

要是陣列中找不到 target ，則回傳 [-1,-1]。

時間複雜度必須是 O(log n)

範例及題目限制

解題思路

相信大家看到這一題，第一秒想到的肯定是 IndexOf, LastIndexOf 吧哈哈

不過時間複雜度那一關就被打死了，因為兩個都是 O(n) ，是達不成條件的…

這時候再認真看看題目，「升幂」、「O(log n)」、「位置(索引)」，是不是很熟悉的關鍵字呢

沒錯! 就應該要想到二分搜尋法 (binary search) 啦!!

我們可以使用跟之前講過的一題幾乎一樣的解決方法 – LeetCode #35 Search Insert Position  尋找陣列中插入的位置

只是因為要找到第一個及最後一個索引，故要使用兩個for來執行

第一個來找第一個索引，第二個就是找最後的

C# 解決方案

方案1

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        int[]res = new int[2]{-1,-1};

        int left = 0;
        int right = nums.Length - 1;

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

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

        left = 0;
        right = nums.Length - 1;

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

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

    }
}

來解釋一下找到值的時候做的判斷

            if (nums[mid] == target) {
                res[0] = mid;
                right = mid-1;
            }

首先會先將目前的索引 mid 更新為暫時的答案

然後下一步會將右邊的邊界設為 mid – 1，再往更前面搜索，要是出現更前面的索引就會更新答案

至於找最後的，那就是對左邊的邊界去做設定，然後往更右邊去搜索了

Java解決方案

方案1

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[]res = new int[]{-1,-1};

        int left = 0;
        int right = nums.length - 1;

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

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

        left = 0;
        right = nums.length - 1;

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

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

Python3 解決方案

方案1

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

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

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

        left = 0
        right = len(nums) - 1

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

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

        return res

JavaScript 解決方案

方案1

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

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

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

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

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

結論

二分搜尋法 (binary search) 是一個可以在特定的環境下快速搜尋的方法，並擁有極高的效率

之後有機會特別寫一篇文章介紹好了~

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

🧡收藏文章或幫我點個廣告，那都是對我的支持

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

題目連結 : Find First and Last Position of Element in Sorted Array – LeetCode

下一題 : LeetCode #35 Search Insert Position  尋找陣列中插入的位置 (簡單來說就是這一題的簡單版)

一些隨機的LeetCode文章

相關文章

發佈留言

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