34. 在排序数组中查找元素的第一个和最后一个位置

约定不等于承诺〃 2024-04-01 18:06 17阅读 0赞

### 34. 在排序数组中查找元素的第一个和最后一个位置 ###

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 \[-1, -1\]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

##### 示例 1： #####

> 输入：nums = \[5,7,7,8,8,10\], target = 8  
> 输出：\[3,4\]

##### 示例 2： #####

> 输入：nums = \[5,7,7,8,8,10\], target = 6  
> 输出：\[-1,-1\]

##### 示例 3： #####

> 输入：nums = \[\], target = 0  
> 输出：\[-1,-1\]

##### 提示： #####

0 < = n u m s . l e n g t h < = 1 0 5 0 <= nums.length <= 10^5 0<=nums.length<=105  
 − 1 0 9 < = n u m s \[ i \] < = 1 0 9 -10^9 <= nums\[i\] <= 10^9 −109<=nums\[i\]<=109  
 n u m s nums nums 是一个非递减数组  
 − 1 0 9 < = t a r g e t < = 1 0 9 -10^9 <= target <= 10^9 −109<=target<=109

#### 方法：（二分查找） ####

#### 法一思路： ####

*  首先处理特殊情况：空数组；targe < nums\[l\]; target > nums\[h\];
 *  二分查找，nums\[m\]<target时，第一个元素肯定在右边，l = mid +1: nums\[m\]>target时，最后一个元素肯定在左边，h = mid -1: 如果nums\[m\] = target,则第一个元素肯定在本位置或者左边，最后一个元素肯定在本位置或者右边；分成两个区间，分别进行二分查找；
 *  左区间找第一个元素，右区间找最后一个元素。

#### 代码：（Java） ####

public class first_last {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [] nums = {
        2,2};
    		int target = 1;
    		int []t = searchRange(nums,target);
    		System.out.print(t[0]);
    		System.out.print(t[1]);
    	}
    	public static int[] searchRange(int[] nums, int target) {
        
    		int [] t = new int[2];
    	    int l = 0, h = nums.length - 1, mid = 0;
    		if(nums.length == 0 || nums[l] > target || nums[h] < target) {
        
    			t[0] = -1;
    			t[1] = -1;
    			return t;
    		}
    		while(l < h) {
        
    			int m = l + (h - l) / 2;
    			if(nums[m] < target) {
        
    				l = m + 1;
    			}else if(nums[m] > target) {
        
    				h = m - 1;
    			}else {
        
    				mid = m;
    				break;
    			}
    		}
    	    if(l == h && nums[l] != target) {
        
    			t[0] = -1;
    			t[1] = -1;
    			return t;
    		}
    		int l1 =mid,  h1 = mid;
    		while(l < h1){
        
    			int m = l + (h1 - l) / 2;
    			if(nums[m] < target) {
        
    				l = m + 1;
    			}else if(l + 1 == h1){
        
    				break;
    			}else {
        
    				h1 = m;
    			}
    		}
    		t[0] = nums[l] == target ? l : h1;
    		while(l1 < h){
        
    			int m = l1 + (h - l1) / 2;
    			if(nums[m] > target) {
        
    				h = m - 1;
    			}else if(l1 + 1 == h){
        
    				break;
    			}else {
        
    				l1 = m;
    			}
    		}
    		t[1] = nums[h] == target ? h : l1;
    		return t;
        }
    }

#### 法二思路： ####

*  可以用二分查找找出第一个位置和最后一个位置，但是寻找的方法有所不同，需要实现两个二分查找。
 *  我们将寻找 target 最后一个位置，转换成寻找 target+1 第一个位置，再往前移动一个位置。
 *  这样我们只需要实现一个二分查找代码即可。

#### 代码：（Java） ####

public class first_last {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [] nums = {
        2,2};
    		int target = 1;
    		int []t = searchRange(nums,target);
    		System.out.print(t[0]);
    		System.out.print(t[1]);
    	}
    	
    	public static int[] searchRange(int[] nums, int target) {
        
    	    int first = findFirst(nums, target);
    	    int last = findFirst(nums, target + 1) - 1;
    	    if (first == nums.length || nums[first] != target) {
        
    	        return new int[]{
        -1, -1};
    	    } else {
        
    	        return new int[]{
        first, Math.max(first, last)};
    	    }
    	}
    
    	private static int findFirst(int[] nums, int target) {
        
    	    int l = 0, h = nums.length; // 注意 h 的初始值
    	    while (l < h) {
        
    	        int m = l + (h - l) / 2;
    	        if (nums[m] >= target) {
        
    	            h = m;
    	        } else {
        
    	            l = m + 1;
    	        }
    	    }
    	    return l;
    	}
    }

##### 复杂度分析; #####

*  时间复杂度： O(log⁡n) ，其中 n 为数组的长度。二分查找的时间复杂度为 O(log⁡n)，一共会执行两次，因此总时间复杂度为 O(log⁡n)。
 *  空间复杂度：O(1)。只需要常数空间存放若干变量。

###### 注：仅供学习参考！ ######

来源：[力扣][Link 1]

[Link 1]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/