Kth ပျောက်ဆုံးနေအပြုသဘောနံပါတ် Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Facebook က Microsoft က
အခင်းအကျင်း တားဆီးခြင်း

မာတိကာ

ပြstatementနာကြေညာချက်

“ Kth Missing Positive Number” ပြproblemနာမှာကျွန်တော်တို့ကို array ထဲထည့်လိုက်တယ် တင်းကြပ်စွာတိုးပွားလာ အမိန့်နှင့်နံပါတ် k ။

ကျွန်ုပ်တို့၏တာ ၀ န်မှာ array ထဲတွင်ပျောက်ဆုံးနေသော Kth positive အရေအတွက်ရှာရန်ဖြစ်သည်။

နမူနာ

arr = [1,2,3,4], k = 2
6

ရှင်းလင်းချက်:

Kth ပျောက်ဆုံးနေအပြုသဘောနံပါတ် Leetcode ဖြေရှင်းချက်

ပေးထားသောခင်းကျင်းပြသမှုအတိုင်းပထမဆုံးပျောက်ဆုံးသောနံပါတ်သည် ၅ ဖြစ်ပြီးဒုတိယပျောက်ဆုံးနေသောနံပါတ်သည် ၆ ဖြစ်သည်။ ထို့ကြောင့်အဖြေမှာ ၆ ဖြစ်သည်။

Brute Force AKth ပျောက်ဆုံးနေအပြုသဘောနံပါတ် Leetcode ဖြေရှင်းချက်များအတွက်ချဉ်းကပ်မှု

ဤပြproblemနာကိုဖြေရှင်းရန် Brute Force ချဉ်းကပ်မှုမှာအောက်ပါအတိုင်းဖြစ်သည်။

  1. ခင်းကျင်းဖြတ်သန်း။
  2. ပျောက်ဆုံးနေသောကိန်းဂဏန်းများကိုကျွန်ုပ်တို့တွက်ချက်တိုင်း။
  3. ပျောက်ဆုံးနေသောအပေါင်းနံပါတ်များသည် k ထက်ကြီးသည် (သို့) ညီမျှသည်ဆိုလျှင် i + k ကိုပြန်သွားပါမည်။
  4. ပျောက်ဆုံးနေသောကိန်းဂဏန်းအရေအတွက်သည် k ထက်နည်းပါကခင်းကျင်းမှု၏ပြီးပြည့်စုံသောဖြတ်သန်းခြင်းပြီးနောက်၊ + k ၏အရွယ်အစားကိုပြန်ပေးလိမ့်မည်။

အကောင်အထည်ဖော်ရေး

Kth ပျောက်ဆုံးနေသောအပြုသဘောဆောင်သောနံပါတ်အတွက် C ++ ကုဒ်

#include <bits/stdc++.h> 
using namespace std; 
    int findKthPositive(vector<int>& arr, int k) {
        for(int i=0;i<arr.size();i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.size()+k;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4};
 int k=2;
 int ans=findKthPositive(arr,k);
 cout<<ans<<endl;
 return 0;
}
6

Kth ပျောက်ဆုံးနေသောအပြုသဘောဆောင်သောနံပါတ်အတွက် Java ကုဒ်

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int findKthPositive(int[] arr, int k) {
        for(int i=0;i<arr.length;i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.length+k;
    }   
  public static void main(String[] args) {
        int [] arr = {1,2,3,4};
        int k=2;
        int ans=findKthPositive(arr,k); 
        System.out.println(ans);
  }
}
6

ရှုပ်ထွေးဆန်းစစ်ခြင်း Kth ပျောက်ဆုံးနေသောအပြုသဘောဆောင်သောနံပါတ် Leetcode ဖြေရှင်းချက်

အချိန်ရှုပ်ထွေး

အထက်ပါကုဒ်၏အချိန်ရှုပ်ထွေးသည် အို (ဎ) ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာအဆိုးဆုံးကိစ္စမှာ O (n) အချိန်ယူတဲ့ linear search တစ်ခုကိုအသုံးပြုနေလို့ပဲ။ ဒီမှာ n ကပေးထားတဲ့ခင်းကျင်း၏အရှည်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အပေါ်ကကုဒ်ရဲ့ရှုပ်ထွေးမှုက အို (၁) ဘာလို့လဲဆိုတော့ငါတို့ကအဖြေကိုသိမ်းဖို့ variable တစ်ခုပဲသုံးတယ်။

Binary Search AKth ပျောက်ဆုံးနေအပြုသဘောနံပါတ် Leetcode ဖြေရှင်းချက်များအတွက်ချဉ်းကပ်မှု

အထက်ပါ algorithm ၏အချိန်ရှုပ်ထွေးမှုသည်အို (n) ဖြစ်သည်။ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည်အဆိုးရွားဆုံးသောအမှု၌ပြီးပြည့်စုံသောခင်းကျင်းမှုကိုဖြတ်ကျော်ရန်လိုအပ်နိုင်သည်။ ကျွန်ုပ်တို့သည် linear ရှာဖွေခြင်းအစား binary search ကိုအသုံးပြုခြင်းအားဖြင့်ဖြေရှင်းချက်၏အချိန်ရှုပ်ထွေးမှုကိုတိုးတက်စေနိုင်သည်။

  1. binary search ကိုရှာဖွေခြင်း၏ပထမ ဦး ဆုံးသတ်မှတ်ကြပါစို့။ ဒီတော့ start က index 0 ဖြစ်လိမ့်မယ်။ end ကပေးထားတဲ့ array ရဲ့နောက်ဆုံး index ဖြစ်လိမ့်မယ်။
  2. ပျောက်ဆုံးနေသောအပြုသဘောဆောင်သည့်ကိန်းဂဏန်းအရေအတွက်သည် k ထက်လျော့နည်းမလာကိုစစ်ဆေးပါမည်။
    1. ထို့နောက်စတင် mid + 1 ဖြစ်လာလိမ့်မည်။
    2. ဒါမှမဟုတ်ရင်အဆုံးကအလယ်ပိုင်းဖြစ်လာလိမ့်မယ်။
  3. အဆုံး + return ပြန်လာပါ။

အကောင်အထည်ဖော်ရေး

Kth ပျောက်ဆုံးနေသောအပြုသဘောဆောင်သောနံပါတ်အတွက် C ++ ကုဒ်

#include <bits/stdc++.h> 
using namespace std; 
int findKthPositive(vector<int>& A, int k) {
        int l = 0, r = A.size(), m;
        while (l < r) {
            m = (l + r) / 2;
            if (A[m] - 1 - m < k)
                l = m + 1;
            else
                r = m;
        }
        return l + k;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4};
 int k=2;
 int ans=findKthPositive(arr,k);
 cout<<ans<<endl;
 return 0;
}
6

Kth ပျောက်ဆုံးနေသောအပြုသဘောဆောင်သောနံပါတ်အတွက် Java ကုဒ်

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int findKthPositive(int[] A, int k) {
        int l = 0, r = A.length, m;
        while (l < r) {
            m = (l + r) / 2;
            if (A[m] - 1 - m < k)
                l = m + 1;
            else
                r = m;
        }
        return l + k;
    }  
  public static void main(String[] args) {
        int [] arr = {1,2,3,4};
        int k=2;
        int ans=findKthPositive(arr,k); 
        System.out.println(ans);
  }
}
6

ရှုပ်ထွေးဆန်းစစ်ခြင်း Kth ပျောက်ဆုံးနေသောအပြုသဘောဆောင်သောနံပါတ် Leetcode ဖြေရှင်းချက်

အချိန်ရှုပ်ထွေး

အထက်ပါကုဒ်၏အချိန်ရှုပ်ထွေးသည် အို (log n) ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာအဆိုးဆုံးမှာ O (logn) အချိန်ကိုယူတဲ့ binary search ကိုသုံးနေလို့ပဲ။ ဒီမှာ n ကပေးထားတဲ့ခင်းကျင်း၏အရှည်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အပေါ်ကကုဒ်ရဲ့ရှုပ်ထွေးမှုက အို (၁) ဘာလို့လဲဆိုတော့ငါတို့ကအဖြေကိုသိမ်းဖို့ variable တစ်ခုပဲသုံးတယ်။

ကိုးကား