K 개의 가장 가까운 요소 찾기

난이도 중급
자주 묻는 질문 아마존
배열 수색조회수 88

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

In K 개의 가장 가까운 요소 찾기 우리가 분류 한 문제 정렬 및 값 x. 문제는 주어진 배열에서 x에 가장 가까운 K 개의 요소를 찾는 것입니다.

arr [] = {12, 16, 22, 30, 35, 39, 42,45, 48, 50, 53, 55, 56} 및 x = 35 배열이 주어집니다. 당신의 임무는 k = 4 가장 가까운 요소를 찾는 것입니다. x에.

결과 : 30,39,42,45

x가 배열에 있으면 출력에서 ​​건너 뜁니다.

암호알고리즘

  1. 이진 검색 방법을 선언하고 정의합니다.
  2. 선언 기능 솔루션 array [], x 및 k 주 함수에서 인수로 전달됩니다.
  3. 솔루션 함수에서 이진 검색 함수를 호출하여 다음 위치를 반환합니다. x에서 cp 솔루션 기능에서.
  4. 세트 n 배열 길이, 왼쪽에서 cp-1, 권리 cp + 1, 0으로 계산합니다.
  5. 반복 while 루프, 배열을 통해 다음 조건을 충족합니다.
    1. left> = 0 및
    2. 오른쪽 <n 및
    3. 카운트 <k
  6. 블록 인 경우 열기 while 루프, 조건은 다음과 같습니다.
    1. x – 배열 [왼쪽]
    2. 배열 [오른쪽] – x
  7. 조건을 만족하면 인쇄 배열 [왼쪽] 및 수행 왼쪽 -.
  8. 위의 조건이 실패하면 인쇄 배열 [오른쪽] 및 수행 맞아 ++ 및 수행 카운트 ++ 루프 내부.
  9. 다음과 같이 주어진 조건으로 if 블록을 엽니 다. (오른쪽 = = n), 열 while 루프 주어진 조건으로 카운트 <k왼쪽> = 0 만족하는 경우 인쇄 배열 [왼쪽] 및 수행 카운트 ++.
  10. 다음과 같이 주어진 조건으로 두 번째 if 블록을 다시 엽니 다. (왼쪽 <0), 열 while 루프 주어진 조건으로 카운트 <k왼쪽> = 0, 만족하는 경우 인쇄 배열 [오른쪽] 및 수행 카운트 ++.

뒤에있는 접근 방식은 먼저 이진 검색을 수행하여 가장 가까운 인덱스를 찾습니다. x. 그런 다음 왼쪽과 오른쪽에서 가장 가까운 K 요소를 검색합니다.

K 개의 가장 가까운 원소 찾기에 대한 설명

그래서 우리는 정렬 된 배열에서 x에 가장 가까운 'k'요소를 찾아야하는 첫 번째 작업이 있습니다. 이를 위해 이진 검색 방법을 사용하여 요소 위치를 찾을 수 있습니다. 그러면 작업이 k 개의 가장 가까운 요소를 더 쉽게 찾을 수 있습니다.

따라서 우리의 주요 아이디어는 x의 위치를 ​​얻고 몇 가지 작업을 수행하고 주어진 배열에서 x와 가장 작은 차이를 갖는 숫자를 찾는 것입니다. 이를 위해 arr [], x 및 k의 인수를 전달합니다. arr, 0, 배열의 길이, 위치를 찾아야하는 개수와 같은 인수는 위치 값을 얻는 이진 검색 함수로 전달됩니다. 이 위치에서 왼쪽 값은 x 바로 앞으로, 오른쪽 값은 x 바로 뒤로 설정합니다. 즉, left = cp -1 (x 바로 앞), 오른쪽은 cp + 1 ( x).

이제 arr [left]가 x 바로 앞의 숫자가 (arr [right] –x)보다 작은 차이 (x – arr [left])를 갖고 있음을 의미하고, x 바로 뒤의 숫자를 의미하고 arr [의 값을 인쇄합니다. left]를하고 왼쪽으로합니다. 그렇지 않으면 arr [right]를 인쇄하고 od count 값을 1 씩 계속 증가시킵니다.

주어진 배열을 가정하십시오.

arr = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56};

x = 35, 위치는 4 개 중 35 개입니다.

여기서 왼쪽 = cp -1 = 3 및 오른쪽 = cp + 1 = 5

따라서 조건을 충족하지 못하는 x – arr [left] <arr [right] – x => 5 <4를 비교합니다.

따라서 else 블록에서는 39 인 arr [right]를 인쇄하고 count = 1 인 right ++ 및 count ++를 수행합니다.

이제 왼쪽 = 3이고 오른쪽은 6이됩니다.

그래서 우리는 x – arr [left] <arr [right] – x => 5 <7, true 조건을 비교합니다.

따라서 if 블록에서는 30 인 arr [left]를 인쇄하고 left- 및 count = 2 인 count ++를 인쇄합니다.

K 개의 가장 가까운 요소 찾기

이제 left = 2, right = 6

그래서 우리는 x – arr [left] <arr [right] – x => 13 <7, true 조건을 비교합니다.

따라서 else 블록에서는 42 인 arr [right]를 인쇄하고 count = 3 인 right ++ 및 count ++를 수행합니다.

이제 left = 2 및 right = 7

따라서 조건을 충족하지 않는 x – arr [left] <arr [right] – x => 13 <7을 비교합니다.

따라서 그렇지 않으면 42 인 arr [right]를 인쇄하고 right ++ 및 count ++ 인 count = 4를 수행합니다.

K 개의 가장 가까운 요소 찾기

이제 카운트 조건이 실패하면 k 개의 가장 가까운 요소를 모두 얻었습니다.

그리고 답은 [39 30 42 45]입니다.

실시

K 개의 가장 가까운 요소를 찾는 C ++ 프로그램

#include<stdio.h>
int Binary_Search(int arr[], int low, int high, int x)
{
    int mid = (low + high)/2;

    if (arr[high] <= x)
        return high;

    if (arr[low] > x)
        return low;

    if (arr[mid] <= x && arr[mid+1] > x)
        return mid;

    if(arr[mid] < x)
        return Binary_Search(arr, mid+1, high, x);

    return Binary_Search(arr, low, mid - 1, x);
}

void solution(int arr[], int x, int k, int num)
{
    int y = Binary_Search(arr, 0, num-1, x);
    int r = y+1;
    int count = 0;

    if (arr[y] == x) y--;
    while (y >= 0 && r < num && count < k)
    {
        if (x - arr[y] < arr[r] - x)
            printf("%d ", arr[y--]);
        else
            printf("%d ", arr[r++]);
        count++;
    }

    while (count < k && y >= 0)
        printf("%d ", arr[y--]), count++;

    while (count < k && r < num)
        printf("%d ", arr[r++]), count++;
}

int main()
{
    int arr[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56};
    int num = sizeof(arr)/sizeof(arr[0]);
    int x = 35;
    int k = 4;
    solution(arr, x, k, num);
    return 0;
}
39 30 42 45

K 개의 가장 가까운 요소를 찾기위한 자바 프로그램

public class kce {

  public static int binarySearch(int[] arr,int low, int high, int x){
    int mid = 0;
    while(low<=high){
      mid = (high+low)/2;
      if(arr[mid] == x){
        return mid;
      }
      else if(x<arr[mid]){
        high = mid-1;
      }
      else{
        low = mid+1;
      }
    }

    return mid;

  }

  public static void solution(int[] arr,int x, int k){
    int cp = binarySearch(arr, 0, arr.length-1, x);
    int n = arr.length-1;
    int left = cp-1;
    int right = cp+1;
    int count = 0;


    while(left>=0 && right<n && count <k){
      if(x-arr[left]< arr[right] -x){
        System.out.print(arr[left--] + " ");
        left--;
      }
      else{
        System.out.print(arr[right++] + " ");
        right++;
      }
      count++;

    }

    if(right == n){
      while(count<k && left>=0){
        System.out.print(arr[left] + " ");
        count++;
      }
    }

    if(left < 0){
      while(count<k && left>=0){
        System.out.print(arr[right] + " ");
        count++;
      }
    }


  }

  public static void main(String[]args){

    int k = 4;
    int x = 35;
    int arr1[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56};
    solution(arr1,x,k);
  }

}
39 30 45 50

복잡성 분석

시간 복잡성

O (Logn + K) 어디에 "엔" 배열의 크기이고 "케이" 우리가 찾아야하는 가장 가까운 요소의 수입니다.

공간 복잡성

확인) 필요한 수의 가장 가까운 요소를 저장합니다.

참조

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