შეამოწმეთ N და მისი ორმაგი არსებობს Leetcode გამოსავალი


Რთული ტური Easy
ხშირად ეკითხებიან Google
Array

პრობლემის განცხადება

ამოცანაში ”შეამოწმეთ N და თუ მისი ორმაგი არსებობს” მოცემულია n ელემენტების მასივი. მასივის სიგრძე ორზე მეტია ან ტოლი.

ჩვენი ამოცანაა შეამოწმოთ, არსებობს თუ არა მასივი წყვილი ისეთი, რომ პირველი მნიშვნელობა გაორმაგდეს მეორე მნიშვნელობით.

უფრო ფორმალურად უნდა გადავამოწმოთ, არსებობს i, j რისთვისაც i

მაგალითი

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

განმარტება:

შეამოწმეთ N და მისი ორმაგი არსებობს Leetcode გამოსავალი

ამ შეყვანის გამოსასვლელი სიმართლეა, რადგან კითხვა გვთხოვს შეამოწმოთ, არის თუ არა რაიმე მნიშვნელობა და მისი ორმაგი გასვლა მოცემულ მასივში, ასე რომ, 7 და 14 აკმაყოფილებს ამ კრიტერიუმებს, რადგან 14 არის 7 – ის ორმაგი.

მიდგომა შეამოწმეთ, თუ N და მისი ორმაგი არსებობს Leetcode გამოსავალი

პირველი მიდგომა ამ პრობლემის გადასაჭრელად არის უხეში ძალის მიდგომა. მასივის თითოეული ელემენტისთვის ჩვენ გადავხედავთ სრულ მასივს და შეამოწმებთ მისი ორმაგად არსებობას. თუ აღმოვაჩენთ ამ პირობის დამაკმაყოფილებელ ელემენტს, მაშინ ვბრუნდებით ჭეშმარიტად, წინააღმდეგ შემთხვევაში, ბოლოს ვუბრუნდებით ყალბი. ამ მიდგომის დროის სირთულეა O (n * n), რადგან მასივის ყველა ელემენტისთვის ჩვენ ვაკვირდებით სრულ მასივს.

ჩვენ შეგვიძლია ამ პრობლემის მოგვარება უკეთეს დროში, სირთულეში, არაორგანიზებული რუკის ან დალაგებული ნაკრების გამოყენებით.

  1. მასივის გადაკვეთა.
  2. მასივის ყველა ელემენტისთვის შეამოწმეთ, არის იგი ორმაგი თუ მისი ნახევარი უკვე არსებობს, ეს არის რუკაზე.
  3. თუ პირობა მართალია, უბრალოდ დააბრუნე true, სხვას დაამატე ეს ელემენტი რუკაზე.
  4. თუ მასივის გადაკვეთა შესრულებულია და ვერ ვხვდებით ვერც ერთი ელემენტის ორმაგს, მაშინ დაბრუნდით false.

განხორციელება

C ++ კოდი, შეამოწმეთ, თუ N და მისი ორმაგი არსებობა

#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

ჯავის კოდი, თუ N და მისი ორმაგი არსებობს, შეამოწმეთ

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 გამოსავალი

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა O (n) იმის გათვალისწინებით, რომ საშუალო დროა სირთულე ჩხრეკისა და უწესრიგო რუქაზე ჩასმა O (1).

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (n) რადგან უარეს შემთხვევაში შეიძლება დაგჭირდეთ ყველა ელემენტის შენახვა.

ლიტერატურა