在排序數組Leetcode解決方案中查找元素的第一個和最後一個位置


難度級別
經常問 亞馬遜 彭博社 ByteDance Facebook 谷歌 Microsoft微軟 神諭 尤伯杯
排列 力碼

問題陳述

在本文標題為“在排序數組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) 因為我們只使用一個變量來存儲答案。

參考