다수 요소

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 골드 피처 블룸버그 게시물에서 ByteDance Facebook 에서 GoDaddy 구글 Microsoft 신탁 섹션 Snapchat 스플 렁크 Yahoo Zenefits
배열조회수 499

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

문제 정책

정렬 된 배열이 주어지면 정렬 된 배열에서 주요 요소를 찾아야합니다. 대다수 요소 : 크기의 절반 이상이 발생하는 수 정렬. 여기에서 우리는 그것이 major_element인지 아닌지 확인해야하는 x를 제공했습니다.

입력

5 2

1 2 2 2 4

산출

2는 주요 요소입니다.

과반수 요소를 찾기위한 접근법 1

우리는 이진 검색의 개념을 사용하지만 까다로운 방식으로 사용합니다. 이진 검색은 주어진 숫자 x의 첫 번째 발생을 확인하기 위해 쉽게 수정할 수 있습니다.

암호알고리즘

1. 배열의 중간 요소가 x인지 아닌지 확인하십시오 .N / 2 회 이상 발생하면 major_element가 배열의 중간에 있어야하기 때문입니다.
2. 있는 경우 사용자 지정 이진 검색을 수행하여 x의 첫 번째 항목을 찾습니다.
3. 얻은 인덱스는 k라고 말하고 (k + N / 2) 번째 인덱스에도 x가 있는지 확인합니다. 그렇다면 x는 다수 요소입니다.

알림: 작업을 쉽게 수행하려면 lower_bound 및 higher_bound STL 함수를 사용하십시오.

실시

과반수 요소를 찾기위한 C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;
int main()
{    
  int n,x;
  cin>>n>>x;  
  int arr[n];
  for(int i=0;i<n;i++)
  {
     cin>>arr[i];
  }
  int low=lower_bound(arr,arr+N,x)-arr; //index of first occurence of the element
  int high=upper_bound(arr,arr+N,x)-arr; //index of the last occurenece of element
  if(high-low>N/2)
    cout<<x <<" is a majority element\n";
  else
    cout<<x <<" is not a majority element\n";
  return 0;
}

과반수 요소 찾기를위한 Java 프로그램

import java.util.Scanner;
class sum
{
    public static int first(int arr[], int low, int high, int x, int n)
    {
        if (high >= low) {
            int mid = low + (high - low) / 2;
            if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)
                return mid;
            else if (x > arr[mid])
                return first(arr, (mid + 1), high, x, n);
            else
                return first(arr, low, (mid - 1), x, n);
        }
        return -1;
    }
    public static int last(int arr[], int low, int high, int x, int n)
    {
        if (high >= low) {
            int mid = low + (high - low) / 2;
            if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x)
                return mid;
            else if (x < arr[mid])
                return last(arr, low, (mid - 1), x, n);
            else
                return last(arr, (mid + 1), high, x, n);
        }
        return -1;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int low=first(a,0,n-1,x,n); //index of first occurence of the element
        int high=last(a,0,n-1,x,n); //index of the last occurenece of element
        if((high-low+1)>n/2)
          System.out.println(x+" is a majority element");
        else
          System.out.println(x+" is not a majority element");
    }
}
5 2
1 2 2 2 4
2 is a majority element

복잡성 분석

시간 복잡성 : O (logN) 우리는 이진 검색의 개념을 사용하고 이진 검색 알고리즘이 O (긴) 시간 복잡성을 가지고 있음을 알고 있기 때문입니다.

공간 복잡성 : O (1) 왜냐하면 우리는 O (1) 또는 일정한 공간 복잡도에 속하는 일부 변수를 사용하기 때문입니다.

과반수 요소를 찾기위한 접근법 2

암호알고리즘

배열의 절반이 될 때까지 반복합니다.
a. 현재 요소가 x이면 (현재 인덱스 + N / 2) 번째 인덱스에 x가 포함되어 있는지 확인합니다.
b. 그렇다면 x는 다수 요소입니다.
c. 그렇지 않으면 x는 major_element가 아닙니다.

실시

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int main()
{  
  int N,x;
  cin>>N>>x;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int end;
  if(N%2)
    end = N/2+1;
  else
    end = N/2;
    
  for(int i=0;i<end;i++)
  {
    if(arr[i] ==x and x == arr[i+N/2])
    {
      cout << x <<" is a mojority element "  <<endl;
      return 0;
    }
  }
  cout<<x<<" is not a majority element\n";
}

자바 프로그램 

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int end;
        if(n%2==1)
          end = n/2+1;
        else
          end = n/2;
        int temp=0;
        for(int i=0;i<end;i++)
        {
          if(a[i] ==x && x == a[i+n/2])
          {
            System.out.println(x+" is a mojority element");
            i=end;
            temp=1;
          }
        }
        if(temp==0)
        System.out.println(x+" is not a majority element");
    }
}
5 2
1 2 3 3 6
2 is not a majority element

복잡성 분석

시간 복잡성: O (N) 왜냐하면 우리는 O (n) 시간 복잡성으로 이끄는 절반 하위 배열을 횡단하기 때문입니다.

공간 복잡성 : O (1) 여기에서는 보조 공간을 사용하지 않기 때문입니다.

참조

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