[LeetCode笔记] 34. Find First and last Position of Element in

前言

　　这题标準运用了二分搜寻法，演算法通常需要使用二分思想，即每次能够排除一半的範围，快速的找出阵列中所要求的元素位置，这样时间複杂度可达 O(log n)，时间複杂度可达 O(n)，这里有 JAVA 和 Python 的写法。

题目

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，找到目标值的开始和结束的位置。
如果在阵列里找不到目标，回传 [-1, -1]。
你必须写出一个时间複杂度 O(log n) 的算法。

题目连结：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

题目限制

0 <= nums.length <= 105
109 <= nums[i] <= 109
nums is a non-decreasing array.
109 <= target <= 109

範例

Input: nums = [5,7,7,8,8,10], target = 8Output: [3,4]

目标值是 8，所以在阵列里开始和结束的位置是 3 和 4

Input: nums = [5,7,7,8,8,10], target = 6Output: [-1,-1]

Input: nums = [], target = 0Output: [-1,-1]

思路&笔记

设计两个函数 findFirst 、 findLast 来取得第一个和最后一个符合 target 值的索引。两个函数内都运用了二分搜寻法来找到正确的索引。findFirst 函数：如果目标元素 target 小于等于 nums[mid]，则将 end 更新为 mid - 1。如果目标元素 target 大于 nums[mid]，则将 start 更新为 mid + 1。在找到目标元素时，将 idx 设定为 mid。确保在找到目标元素时继续向左搜寻，以找到第一次出现的位置。findLast 函数：如果目标元素 target 大于等于 nums[mid]，则将 start 更新为 mid + 1。如果目标元素 target 小于 nums[mid]，则将 end 更新为 mid - 1。在找到目标元素时，将 idx 设定为 mid。确保在找到目标元素时继续向右搜寻，以找到最后一次出现的位置。

[注意点] 之所以要用上述中间值的写法会比较安全，因如果 start 和 end 趋近于最大数时，两者相加起来的合可能会造成整数溢位

JAVA 实现

class Solution {    public int[] searchRange(int[] nums, int target) {        int[] result = new int[2];        result[0] = findFirst(nums, target); // target 第一次出现的位置        result[1] = findLast(nums, target); // target 最后一次出现的位置        return result;    }    public int findFirst(int[] nums, int target){        int idx = -1; // 回传值        int start = 0; // 起点位置        int end = nums.length - 1; // 终点位置        while(start <= end){            int mid = (start + end) / 2; // 中位数            // 一直往阵列的左侧找到底，找到第一次出现的位置            if(target <= nums[mid]){                end = mid - 1; // 重新定义终点，下次回圈找到新的终点停止            }else{                start = mid + 1; // 重新定义起点，下次回圈从新的起点开始            }            if (target == nums[mid]) { // 阵列里确定有 target                idx = mid;            }        }        return idx;    }    public int findLast(int[] nums, int target){        int idx = -1;        int start = 0;        int end = nums.length - 1;        while (start <= end){           int mid = (start + end) / 2;           // 一直往阵列的右侧找到底，找到最后一次出现的位置           if(target >= nums[mid]){               start = mid + 1;           }else{               end = mid - 1;           }           if(target == nums[mid]){               idx = mid;           }        }        return idx;    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def searchRange(self, nums: List[int], target: int) -> List[int]:        result = [self.findFirst(nums, target), self.findLast(nums, target)]        return result    def findFirst(self, nums: List[int], target: int) -> int:        idx = -1        start, end = 0, len(nums) - 1        while start <= end:            mid = (start + end) // 2            if target <= nums[mid]:                end = mid - 1            else:                start = mid + 1            if target == nums[mid]:                idx = mid        return idx    def findLast(self, nums: List[int], target: int) -> int:        idx = -1        start, end = 0, len(nums) - 1        while start <= end:            mid = (start + end) // 2            if target >= nums[mid]:                start = mid + 1            else:                end = mid - 1            if target == nums[mid]:                idx = mid        return idx

成绩

LanguageRuntimeMemoryJava0ms45.74MBPython75ms17.81MB

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2024/01/21/Leetcode-34-Find-First-and-last-Position-of-Element-in-Sorted-Array-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论