정렬되지 않은 배열에서 홀수 발생이있는 두 숫자 찾기

난이도 쉽게
자주 묻는 질문 수행자 팩트 셋 구글 신탁
배열조회수 333

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

링크드 인버퍼레딧텀블러

문제 정책

"정렬되지 않은 배열에서 홀수 발생이있는 두 숫자 찾기"문제에서 우리는 정렬되지 않은 정렬. 두 숫자가 아닌이 배열에서 다른 모든 숫자는 짝수 번 발생합니다. 홀수 번 발생하는 두 숫자를 찾으십시오.

참고 : 배열은 홀수 번 발생하는 정확히 두 개의 숫자를 포함해야합니다.

입력 형식

정수 n을 포함하는 첫 번째이자 유일한 행입니다.

공백으로 구분 된 n 개의 정수를 포함하는 두 번째 줄.

출력 형식

공백으로 구분 된 두 개의 정수를 포함하는 첫 번째 및 유일한 행입니다.

예

5 5 4 6 6 7
4 7

설명 : 주요 아이디어는 비트 XOR을 사용하는 것입니다. 예를 들어 4와 7의 XOR은 4 (100) ^ 7 (111) = 011입니다.

XOR의 속성

i) 임의의 숫자의 XOR은 0 즉, x ^ x = 0을 제공합니다.
II) 0이있는 숫자의 XOR은 숫자를 제공합니다. 즉, x ^ 0 = x

정렬되지 않은 배열에서 홀수 발생이있는 두 숫자를 찾는 알고리즘

정렬되지 않은 숫자 배열이 주어집니다. 모든 숫자는 홀수 번 발생하는 두 번을 제외하고 짝수 번 발생합니다. 두 숫자를 a 및 b 홀수 번 발생합니다. 배열의 모든 요소를 ​​xor하여 변수에 저장합니다. 이것은 xor를 줄 것입니다 a 및 b . 다른 모든 요소는 짝수 번 발생하고 xor 자체가 XNUMX이기 때문입니다.

배열 [2,2,5,4,6,6]이 있다고 가정합니다. 모든 요소의 Xor = 5 ^ 4.

이제 우리는 모든 요소의 xor를 취한 후 xor의 세트 비트가이 위치에서 a 조금 또는 b 비트를 설정했습니다. 이 경우이 위치에서 출력에 설정된 비트로 이어지기 때문입니다. 따라서 모든 요소의 최종 xor에있는 모든 세트 비트는 해당 비트가 a 및 b 다르다.

5 (101) 및 4 (100)의 Xor는 (001)입니다. 우리는 두 숫자에서 가장 왼쪽 비트가 다르다는 것을 알 수 있습니다. 그래서 우리는이 문제를 해결하기 위해이 개념을 사용할 수 있습니다. 우리는 xor에서 약간의 시간을 가져갑니다. xor의 가장 오른쪽 세트 비트를 취한다고 가정 해 보겠습니다. 그리고 두 개의 숫자를 저장하기 위해 두 개의 변수를 사용합니다. 배열의 모든 요소를 ​​두 세트로 나눕니다. 첫 번째는 해당 비트 세트가있는 요소이고 두 번째는 해당 비트가 설정되지 않은 요소입니다.

[2,2,5,4,6,6]

가장 오른쪽 비트가 설정된 숫자 (001). 

두 세트는 – 

  1. [5]
  2. [2,2,4,6,6]

두 세트의 모든 요소를 ​​xor 한 후 홀수 번 발생하는 두 개의 숫자를 얻습니다. 이 세트의 모든 요소를 ​​xor 한 후 5와 4를 얻습니다. 가장 오른쪽에 설정된 비트로 숫자를 얻으려면 – 

먼저 가장 오른쪽에 설정된 비트를 제거한 다음 숫자로 xor 한 다음 가장 오른쪽에 설정된 비트를 가진 숫자를 얻습니다. 맨 오른쪽 세트 비트를 제거하려면 – a & (a-1).

실시

정렬되지 않은 배열에서 홀수 발생이있는 두 숫자를 찾는 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

vector<int> two_odd_occuring_elements(vector<int> a, int n)  {
    int xr=0;
    for(int i=0;i<n;i++){
        xr^=a[i];
    }
    int one=0,two=0;
    xr = xr^(xr&(xr-1));
    for(int i=0;i<n;i++){
        if((xr&a[i])==0){
            one^=a[i];
        }else{
            two^=a[i];
        }
    }
    return {one,two};
}

int main() {
  int n;
  cin>>n;
  vector<int> v;
  for(int i=0;i<n;i++){
    int x;cin>>x;
    v.push_back(x);
  }
  vector<int> ans = two_odd_occuring_elements(v,n);
  cout<<ans[0]<<" "<<ans[1]<<endl;
  
  return 0;
}

정렬되지 않은 배열에서 홀수 발생이있는 두 숫자를 찾는 Java 프로그램

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        two_odd_occuring_elements(arr,n);
  }
  
  public static void two_odd_occuring_elements(int[] a,int n){
        int xr=0;
        for(int i=0;i<n;i++){
          xr^=a[i];
      }
      int one=0,two=0;
      xr = xr^(xr&(xr-1));
      for(int i=0;i<n;i++){
          if((xr&a[i])==0){
              one^=a[i];
          }else{
              two^=a[i];
          }
      }
      System.out.print(one+" "+two+"\n");
    }
    
    public static void swap(int a, int b) 
    { 
        int temp = a; 
        a = b; 
        b = temp; 
    } 

}
8
4 2 4 5 2 3 3 1
1 5

정렬되지 않은 배열에서 홀수 발생이있는 두 숫자를 찾기위한 복잡성 분석

시간 복잡성

O (N) 어디에 n 주어진 배열의 크기입니다. 여기서 우리는 요소별로 전체 배열 요소를 탐색하고 일정한 시간에 일부 작업을 수행합니다.

공간 복잡성

O (1) 여기에 보조 공간을 만들지 않기 때문입니다.

링크드 인버퍼레딧텀블러
균열 시스템 설계 인터뷰
Translate »