在排序数组Leetcode解决方案中查找元素的第一个和最后一个位置


难度级别 中等
经常问 亚马逊 彭博 ByteDance Facebook 谷歌 微软 神谕 尤伯杯
排列 力码

问题陈述

在标题为“排序数组Leetcode解决方案中元素的第一个和最后一个位置”的文章中,我们将讨论leetcode问题的解决方案。 在给定的问题中,我们得到一个数组。 我们还获得了目标元素。 数组中的元素按升序排序。

我们需要找到目标元素在排序数组中的第一个和最后一个位置。

如果目标元素不存在,则返回[-1,-1]。

使用案列

array: [1,2,5,5,5,9] , target=5
[2,4]

说明:

在排序数组Leetcode解决方案中查找元素的第一个和最后一个位置

就像给定的排序数组一样,5第一次出现在索引编号2处,最后一次出现在索引编号4处。

途径

解决此问题的幼稚方法是扫描整个数组,并在我们第一次和最后一次遇到目标时返回索引。 该算法的时间复杂度为O(n),因为在最坏的情况下,我们可能需要遍历整个数组。

随着元素按升序排序,我们可以利用它。 尽管进行了线性搜索,我们仍将使用 二进制搜索 查找目标元素的第一个和最后一个匹配项。 该二进制搜索代码与普通的二进制搜索代码略有不同,在常规的二进制搜索代码中,我们检查元素是否存在于已排序的数组中。

这些是常规二进制搜索代码中的细微变化:

  1. 找到目标元素后,程序不会立即终止。 我们将运行循环直到start = end。
  2. 另一个更改是在arr [mid] == target的时候。
    1. 对于第一次出现,end = mid-1。
    2. 对于最后一次出现,start = mid + 1。

代码在排序数组Leetcode解决方案中查找元素的第一个和最后一个位置

C ++代码

#include <bits/stdc++.h> 
using namespace std; 
    int findFirst(vector<int>& nums, int target)
    {
         int ans = -1;
    int s = 0;
    int e = nums.size() - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            e = mid - 1;
        }
    }
    return ans;
    }
     int findLast(vector<int>& nums, int target)
    {
          int ans = -1;
    int s = 0;
    int e = nums.size() - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            s = mid + 1;
        }
    }
    return ans;
    }
    vector<int> find(vector<int>& nums, int target) {
        vector<int>result(2);
         result[0] = findFirst(nums, target);
         result[1] = findLast(nums, target);
         return result;
    }

int main() 
{ 
 vector<int> arr = {1,2,5,5,5,9}; 
int target=5;
vector<int> ans(2);
ans=  find(arr,target);
for(int i=0;i<2;i++)
 cout<<ans[i]<<" "; 
 return 0;
}
[2,4]

Java代码

import java.util.Arrays; 
public class Tutorialcup {
    public static int[] find(int[] nums, int target) {
    int[] result = new int[2];
    result[0] = findFirst(nums, target);
    result[1] = findLast(nums, target);
    return result;
}

private static int findFirst(int[] nums, int target){
    int ans = -1;
    int s = 0;
    int e = nums.length - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            e = mid - 1;
        }
    }
    return ans;
}
    

private static int findLast(int[] nums, int target){
       int ans = -1;
    int s = 0;
    int e = nums.length - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            s = mid + 1;
        }
    }
    return ans;
}
  public static void main(String[] args) {
    int [] arr = {1,2,5,5,5,9}; 
    int target=5;
     int[] ans = new int[2];
    ans=  find(arr,target);
    System.out.println(Arrays.toString(ans));
  }
}
[2,4]

复杂度分析

时间复杂度

上面代码的时间复杂度是 O(log(n))其中n是数组的大小。 因为我们在二进制搜索过程中最多处理log(n)个元素。

空间复杂度

上面代码的空间复杂度是 O(1) 因为我们只使用一个变量来存储答案。

參考資料