Գտեք տարրի առաջին և վերջին դիրքը տեսակավորված զանգվածի Leetcode լուծույթում  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Bloomberg ByteDance facebook Google Microsoft Պատգամախոս Uber
ալգորիթմները Դասավորություն կոդավորում հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions

Խնդրի հայտարարություն  

«Գտեք տարրի առաջին և վերջին դիրքը տեսակների զանգվածի տեսակավորված լուծման լուծում» վերնագրով այս հոդվածում մենք կքննարկենք leetcode խնդրի լուծումը: Տրված խնդրում մեզ զանգված է տրվում: Մեզ նույնպես տրվում է թիրախային տարր: Rayանգվածի տարրերը հաջորդականորեն դասվում են ըստ աճող հերթականության:

Մենք պետք է գտնենք նպատակային տարրի առաջին և վերջին դիրքը տեսակավորված զանգվածում:

Եթե ​​թիրախային տարրը առկա չէ, ապա վերադարձիր [-1, -1]:

Օրինակ  

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

Բացատրությունը.

Գտեք տարրի առաջին և վերջին դիրքը տեսակավորված զանգվածի Leetcode լուծույթում

Ինչպես տրված տեսակավորված զանգվածում, 5-ը առաջին անգամ հայտնվում է թիվ 2 ցուցիչում, իսկ վերջին անգամ ՝ թիվ 4 ցուցիչում:

Մոտեցում  

Այս խնդրի լուծման միամիտ մոտեցումն է ամբողջ զանգվածը սկանավորելը և ինդեքսը վերադարձնելը, երբ մենք առաջին անգամ ենք հանդիպում վերջին անգամ և վերջին անգամ: Alամանակի բարդությունն այս ալգորիթմի համար O (n) է, քանի որ վատագույն դեպքում մեզ կարող է անհրաժեշտ լինել անցնել ամբողջական զանգվածը:

Քանի որ տարրերը դասավորված են աճող կարգի համաձայն, մենք կարող ենք օգտվել դրանից: Չնայած գծային որոնում կատարելուն, մենք կօգտագործենք a Երկուական որոնում գտնել նպատակային տարրի առաջին և վերջին դեպքերը: Այս երկուական որոնման կոդը մի փոքր կտարբերվի սովորական երկուական որոնման ծածկագրից, որտեղ մենք ստուգում ենք ՝ արդյոք տարրը առկա է տեսակավորված զանգվածում, թե ոչ:

Տես նաեւ,
Տպեք հաջորդ Q մեծ թվով հարցումները

Սրանք նորմալ երկուական որոնման կոդի փոքր փոփոխություններ են.

  1. Targetրագիրը չի դադարի անմիջապես թիրախային տարրը գտնելուց հետո: Մենք կաշխատենք օղակը մինչև սկիզբ = ավարտ:
  2. Մեկ այլ փոփոխություն այն կետում է, որտեղ arr [mid] == նպատակն է:
    1. Առաջին դեպքի ավարտի համար = 1-ի կես:
    2. Եվ վերջին իրադարձության համար սկսեք = կես + 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]

Բարդության վերլուծություն  

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (տեղեկամատյան (n))որտեղ n - զանգվածի չափը: Քանի որ մենք երկուական որոնման ընթացքում մշակում ենք առավելագույն տեղեկամատյան (n) տարրեր:

Տես նաեւ,
Գտեք Lucky Integer- ը զանգվածի Leetcode լուծման մեջ

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է Ո (1) քանի որ մենք պատասխաններ պահելու համար օգտագործում ենք միայն փոփոխական:

Սայլակ