N နှင့်၎င်း၏နှစ်ဆ Leetcode Solution ရှိမရှိစစ်ဆေးပါ


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

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

ပြIfနာ၌“ Check If N နှင့်၎င်း၏နှစ်ဆတည်ရှိမှုကိုစစ်ဆေးပါ” တွင်ကျွန်ုပ်တို့အား n element များစွာကိုပေးထားသည်။ Array length သည်နှစ်ခုထက်ကြီးသည် (သို့) ညီမျှသည်။

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

ပိုပြီးတရားဝင်အနေဖြင့် i, j အနေဖြင့် i ရှိ၊ မရှိကိုစစ်ဆေးရန်လိုအပ်သည်

နမူနာ

arr = [7,1,14,11]
true

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

N နှင့်၎င်း၏နှစ်ဆ Leetcode Solution ရှိမရှိစစ်ဆေးပါ

ဘာလို့လဲဆိုတော့မေးခွန်းကပေးထားတဲ့ခင်းကျင်းချက်ထဲမှာတန်ဖိုးတစ်ခုနှင့် ၄ င်းရဲ့နှစ်ဆထွက်ရှိမှုရှိမရှိကိုစစ်ဆေးဖို့တောင်းဆိုထားလို့ပါ။ ဒီတော့ 7 နဲ့ 14 ကဒီစံနှုန်းတွေနဲ့ကိုက်ညီတယ်။ 14 က ၇ ရဲ့နှစ်ဆဖြစ်တယ်။

N နှင့်၎င်း၏နှစ်ဆ Leetcode ဖြေရှင်းချက်ရှိပါက Check များအတွက်ချဉ်းကပ်မှု

ဤပြproblemနာကိုဖြေရှင်းရန်ပထမဆုံးချဉ်းကပ်နည်းမှာ brute အင်အားစု ချဉ်းကပ်နည်း။ array ထဲရှိ element တစ်ခုစီအတွက်ကျွန်ုပ်တို့ array အပြည့်ကိုဖြတ်ပြီး၎င်းသည်နှစ်ဆရှိမရှိစစ်ဆေးပါလိမ့်မည်။ ဤအခြေအနေကိုကျေနပ်စေသော element တစ်ခုကိုတွေ့ရှိပါကကျွန်ုပ်တို့သည် true သို့ပြန်သွားပါလိမ့်မည်။ ဒီချဉ်းကပ်မှုအတွက်အချိန်ရှုပ်ထွေးမှုသည်အို (n * n) ဖြစ်သည်။ အဘယ်ကြောင့်ဆိုသော်ခင်းကျင်းဖွဲ့စည်းမှု၏အစိတ်အပိုင်းတိုင်းအတွက်ကျွန်ုပ်တို့သည်ပြီးပြည့်စုံသောခင်းကျင်းမှုကိုဖြတ်သန်းနေသောကြောင့်ဖြစ်သည်။

ကျွန်ုပ်တို့သည်ဤပြproblemနာကိုအချိန်ကာလရှုပ်ထွေးမှုမရှိဘဲအလွယ်တကူမသတ်မှတ်ထားသောမြေပုံသို့မဟုတ်နံပါတ်စဉ်မရှိသောအစုံကို သုံး၍ ဖြေရှင်းနိုင်သည်

  1. ခင်းကျင်းဖြတ်သန်း။
  2. array ထဲရှိ element တိုင်းအတွက်နှစ်ဆဖြစ်စေ (သို့) တစ်ဝက်ရှိမရှိမြေပုံကိုစစ်ဆေးပါ။
  3. အကယ်၍ အခြေအနေမှန်ကန်ပါက၊ return ပြန်ပါကအခြား element ကိုမြေပုံထဲသို့ထည့်ပါ။
  4. တကယ်လို့ array traversal ပြီးသွားရင် element ရဲ့ double ကိုရှာမတွေ့ဘူးဆိုရင် false ကိုပြန်သွားပါ။

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

Check If N နှင့်ယင်း၏နှစ်ဆတည်ရှိရန်အတွက် C ++ ကုဒ်

#include <bits/stdc++.h> 
using namespace std; 
    bool checkIfExist(vector<int>& arr) {
      unordered_map<int,bool>mp;
        for(int i=0;i<arr.size();i++)
        {
            if(mp[arr[i]*2]==1||(mp[arr[i]/2]==1&&arr[i]%2==0))
                return true;
            mp[arr[i]]=1;
        }
        return false;
    }
int main() 
{ 
 vector<int> arr = {7,1,14,11}; 
 bool ans=checkIfExist(arr);
 cout <<boolalpha;
 cout<<ans<<endl;
 return 0;
}
true

Check If N နှင့်၎င်း၏နှစ်ဆတည်ရှိရန်အတွက် Java code

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static boolean checkIfExist(int[] arr) {
        Set<Integer> seen = new HashSet<>();   
        for (int i : arr) {
            if (seen.contains(2 * i) || (i % 2 == 0 && seen.contains(i / 2)))
                return true;
            seen.add(i);
        }
        return false;
    }
  public static void main(String[] args) {
        int [] arr = {7,1,14,11}; 
        boolean ans=checkIfExist(arr); 
        System.out.println(ans);
  }
}
true

စစ်ဆေးမှု၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း အကယ်၍ N နှင့် Leetcode Solution သည် ၄ ​​င်း၏ Double တည်ရှိပါက

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

အထက်ပါကုဒ်၏အချိန်ရှုပ်ထွေးသည် အို (ဎ) နံပါတ်စဉ်အလိုက်သတ်မှတ်ထားသောမြေပုံတွင်ရှာဖွေခြင်းနှင့်ထည့်သွင်းခြင်း၏ပျမ်းမျှအချိန်ရှုပ်ထွေးမှုကို O (1) အဖြစ်သတ်မှတ်ခြင်း။

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

အပေါ်ကကုဒ်ရဲ့ရှုပ်ထွေးမှုက အို (ဎ) ဘာလို့လဲဆိုတော့အဆိုးဆုံးအခြေအနေမှာ element တွေအားလုံးကိုသိမ်းထားဖို့လိုတာပေါ့။

ကိုးကား