Знайти першу та останню позиції елемента у розв’язаному сортуваному масиві


Рівень складності Medium
Часто запитують у Амазонка Bloomberg ByteDance Facebook Google Microsoft оракул Убер
масив LeetCode

Постановка проблеми

У цій статті під назвою «Знайти першу та останню позиції елемента у розв’язаному матричному рішенні штрих-коду» ми обговоримо рішення проблеми лет-коду. У даній задачі нам дано масив. Нам також дають цільовий елемент. Елементи масиву послідовно збільшуються.

Нам потрібно знайти першу і останню позиції цільового елемента в відсортованому масиві.

Якщо цільового елемента немає, поверніть [-1, -1].

Приклад

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

Пояснення:

Знайти першу та останню позиції елемента у розв’язаному сортуваному масиві

Як і в даному відсортованому масиві, 5 вперше з’являється під номером 2, а востаннє - під номером 4.

Підхід

Наївний підхід до вирішення цієї проблеми полягає у скануванні всього масиву та поверненні індексу, коли ми вперше та востаннє стикаємось із ціллю. Складність часу для цього алгоритму становить O (n), оскільки в найгіршому випадку нам може знадобитися пройти повний масив.

Оскільки елементи сортуються за зростанням, ми можемо цим скористатися. Незважаючи на лінійний пошук, ми будемо використовувати Binary search щоб знайти перше та останнє входження цільового елемента. Цей двійковий код пошуку буде трохи відрізнятися від звичайного двійкового коду пошуку, де ми перевіряємо, чи присутній елемент у відсортованому масиві чи ні.

Ось невеликі зміни в звичайному двійковому коді пошуку:

  1. Програма не припиняється відразу після пошуку цільового елемента. Ми будемо запускати цикл до початку = кінця.
  2. Ще одна зміна - у точці, де arr [mid] == target.
    1. Для першого випадку end = середина 1.
    2. І для останнього випадку start = середина + 1.

Код Знайти першу та останню позиції елемента у розсортованому масиві Рішення Leetcode

Код С ++

#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 (журнал (n))де n - розмір масиву. Оскільки під час двійкового пошуку ми обробляємо щонайбільше елементів журналу (n).

Космічна складність

Складність простору наведеного коду становить O (1) тому що ми використовуємо лише змінну для зберігання відповідей.

посилання