N과 이중 존재하는 Leetcode 솔루션 확인

난이도 쉽게
자주 묻는 질문 구글
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 107

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 설명

”Check If N and Its Double Exist”문제에서 n 개의 요소 배열이 주어집니다. 배열 길이가 XNUMX보다 크거나 같습니다.

우리의 임무는 첫 번째 값이 두 번째 값의 두 배가되도록 배열에 쌍이 있는지 확인하는 것입니다.

좀 더 공식적으로 i, j가 존재하는지 확인해야합니다.

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

설명 :

N과 이중 존재하는 Leetcode 솔루션 확인

이 입력에 대한 출력은 true입니다. 질문은 주어진 배열에서 값과 이중 종료가 있는지 확인하도록 요청하기 때문입니다. 따라서 7과 14는 14가 7의 두 배이므로 이러한 기준을 충족합니다.

N과 그 이중 존재 Leetcode 솔루션에 대한 접근 방식

이 문제를 해결하는 첫 번째 방법은 브 루트 포스 접근하다. 배열의 각 요소에 대해 전체 배열을 탐색하고 이중이 있는지 확인합니다. 이 조건을 만족하는 요소를 찾으면 true를 반환하고, 그렇지 않으면 마지막에 false를 반환합니다. 이 접근법의 시간 복잡도는 O (n * n)입니다. 배열의 모든 요소에 대해 전체 배열을 순회하기 때문입니다.

순서가 지정되지 않은 맵 또는 순서가 지정되지 않은 집합을 사용하여 더 나은 시간 복잡성으로이 문제를 해결할 수 있습니다.

  1. 배열을 횡단합니다.
  2. 배열의 모든 요소에 대해 이중 또는 절반이 이미 존재하는지 확인하십시오.
  3. 조건이 true이면 true를 반환하고 그렇지 않으면 해당 요소를지도에 추가합니다.
  4. 배열 순회가 완료되고 이중 요소를 찾지 못한 경우 false를 반환합니다.

실시

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

N 및 이중 존재 여부 확인을위한 Java 코드

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

Check If N 및 이중 존재 Leetcode 솔루션의 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (N) 정렬되지 않은 맵에서 검색하고 삽입하는 평균 시간 복잡성을 O (1)로 간주합니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (N) 최악의 경우 모든 요소를 ​​저장해야 할 수도 있기 때문입니다.

참조

균열 시스템 설계 인터뷰
Translate »