געפֿינען די ערשטע און לעצטע שטעלע פון ​​עלעמענט אין די סאָרטעד אַרייז לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן בלומבערג ביטעדאַנסע facebook גוגל מייקראָסאָפֿט אָראַקל ובער
מענגע LeetCode

פּראָבלעם דערקלערונג

אין דעם אַרטיקל טייטאַלד "געפֿינען די ערשטע און לעצטע שטעלע פון ​​עלעמענט אין סאָרטעד אַרעע Leetcode לייזונג," מיר וועלן דיסקוטירן די לייזונג צו אַ לעעטקאָדע פּראָבלעם. אין דער געגעבן פּראָבלעם מיר זענען געגעבן אַ מענגע. מיר אויך באַקומען אַ ציל עלעמענט. עלעמענטן אין דער מענגע זענען סיקוואַנסיד אין ינקריסינג סדר.

מיר דאַרפֿן צו געפֿינען די ערשטע און לעצטע שטעלע פון ​​דער ציל עלעמענט אין די סאָרטעד מענגע.

אויב דער ציל עלעמענט איז נישט פאָרשטעלן, צוריקקומען [-1, -1].

בייַשפּיל

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

דערקלערונג:

געפֿינען די ערשטע און לעצטע שטעלע פון ​​עלעמענט אין די סאָרטעד אַרייז לעעטקאָדע סאַלושאַן

ווי אין די געגעבן סאָרטעד מענגע, 5 איז דער ערשטער מאָל אין אינדעקס נומער 2 און לעצטע מאָל אין אינדעקס נומער 4.

צוגאַנג

די נאַיוו צוגאַנג צו סאָלווע דעם פּראָבלעם איז צו יבערקוקן די גאנצע מענגע און צוריקקומען די אינדעקס ווען מיר טרעפן די ציל פֿאַר די ערשטער מאָל און לעצטע מאָל. די צייט קאַמפּלעקסיטי פֿאַר דעם אַלגערידאַם איז אָ (n), ווייַל אין די ערגסט פאַל מיר דאַרפֿן צו דורכגיין די גאַנץ מענגע.

ווען די יסודות זענען אויסגעשטעלט אין ינקריסינג סדר, מיר קענען נוצן עס. טראָץ אַ לינעאַר זוכן, מיר וועלן נוצן אַ ביינערי זוכן צו געפֿינען די ערשטע און לעצטע פֿאַלן פון די ציל עלעמענט. די ביינערי זוכן קאָד וועט זיין אַ ביסל אַנדערש פון די נאָרמאַל ביינערי זוכן קאָד, אויב מיר קאָנטראָלירן אויב דער עלעמענט איז פאָרשטעלן אין די סאָרטעד מענגע אָדער נישט.

דאָס זענען די קליין ענדערונגען אין נאָרמאַל ביינערי זוכן קאָד:

  1. דער פּראָגראַם וועט ניט פאַרענדיקן גלייך נאָך דערגייונג דער ציל עלעמענט מיר וועלן לויפן די שלייף ביז אָנהייב = סוף.
  2. אן אנדער ענדערונג איז בייַ די פונט ווו אַרר [מיטן] == ציל.
    1. פֿאַר דער ערשטער פּאַסירונג סוף = מיטן -1.
    2. און פֿאַר די לעצטע פּאַסירונג אָנהייב = מיטן 1.

קאָד געפֿינען די ערשטע און לעצטע שטעלע פון ​​עלעמענט אין די סאָרטעד עריי לעעטקאָדע לייזונג

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]

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

די צייט קאַמפּלעקסיטי פון די אויבן קאָד איז אָ (קלאָץ (n))ווו n איז די גרייס פון דעם מענגע. ווייַל מיר זענען ביי מערסטנס פּראַסעסינג לאָג (n) עלעמענטן בעשאַס די ביינערי זוכן.

אָרט קאַמפּלעקסיטי

די פּלאַץ קאַמפּלעקסיטי פון די אויבן קאָד איז אָ (1) ווייַל מיר נוצן בלויז אַ בייַטעוודיק צו קראָם ענטפֿערס.

רעפֿערענצן