k보다 작거나 같은 모든 요소를 함께 가져 오는 데 필요한 최소 스왑-TutorialCup

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

Twitter Facebook 링크드인 버퍼 레딧 텀블러

"k보다 작거나 같은 모든 요소를 함께 가져 오는 데 필요한 최소 스왑"문제는 정수가 있음을 나타냅니다. 정렬. 문제 설명은 주어진 숫자 k보다 작거나 같은 요소를 모으는 데 필요한 최소 스왑 수를 알아 내도록 요청합니다.

차례

예

arr[]={4,6,1,3,2}, k = 4

설명

1 개의 스왑 만 필요합니다. 6을 2로 바꿔서 4, 2, 1, 3이 합쳐 지도록 할 수 있습니다.

암호알고리즘

k보다 작은 모든 요소의 개수를 가져옵니다.
k보다 큰 모든 요소의 개수를 가져옵니다.
더 작은 값으로 출력을 설정합니다.
i = 0 및 j = 개수에서 배열을 횡단합니다.
1. array [i]가 k 값보다 큰지 확인한 다음 small 값을 1만큼 줄입니다.
2. array [j]가 k 값보다 큰지 확인한 다음 small 값을 1 씩 늘립니다.
3. 출력과 작은 것 사이의 최소값을 찾아 출력에 저장하십시오.
출력값을 반환합니다.

설명

우리는 정렬 of 정수, k라는 정수 값을 사용하여 k보다 작거나 같은 모든 요소를 모으기 위해 필요한 최소 스왑 수를 알아 내도록 요청했습니다. 최소한의 스왑 만 찾으면됩니다.

이를 위해 k보다 작거나 같은 요소의 수를 세고 더 작은 변수에 저장할 것입니다. 따라서 더 작은 변수는 k보다 작거나 같은 더 작은 수의 개수를 보유합니다. 그 개수와 유사하게, 우리는 숫자 k보다 큰 모든 숫자를 계산합니다. 출력 값을 더 작게 설정하고 나중에이 출력과 값을 비교하고 동시에 저장합니다. 위에서 언급 한 예를 들어 보면 4는 작은 개수이고 1은 큰 개수입니다.

i = 0, j = 더 작게 배열을 가로 지르고, array [i]와 arr [j]가 k 값보다 큰지 확인하고, arr [i]가 다음보다 크면 array [j]이면 더 작은 개수를 줄입니다. 더 크면 더 작은 수를 늘립니다.

동시에 우리는 출력과 더 작은 수 사이의 최소값을 알아낼 것입니다. 우리가 횡단하는 루프에서 더 작은 값을 줄이고 더 작은 값을 늘리기 위해 두 작업을 모두 수행하고 있습니다. 마지막으로 출력 값을 반환하면됩니다. 원하는 출력을 얻을 수 있기 때문입니다.

핀

암호

k보다 작거나 같은 모든 요소를 함께 가져 오는 데 필요한 최소 스왑을 찾는 C ++ 코드

#include <iostream>

using namespace std;

int minimumSwapToK(int arr[], int n, int k)
{
    int count = 0;
    for (int i = 0; i < n; ++i)
        if (arr[i] <= k)
            ++count;

    int bad = 0;
    for (int i = 0; i < count; ++i)
        if (arr[i] > k)
            ++bad;

    int ans = bad;
    for (int i = 0, j = count; j < n; ++i, ++j)
    {

        if (arr[i] > k)
            --bad;

        if (arr[j] > k)
            ++bad;

        ans = min(ans, bad);
    }
    return ans;
}

int main()
{
    int arr[] = {4,6,1,3,2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4;
    int result = minimumSwapToK(arr, n, k);
    cout <<result;
    return 0;
}

k보다 작거나 같은 모든 요소를 함께 가져 오는 데 필요한 최소 스왑을 찾는 Java 코드

class minimumSwaps
{
    public static int minimumSwapToK(int arr[], int n, int k)
    {

        int count = 0;
        for (int i = 0; i < n; ++i)
            if (arr[i] <= k)
                ++count;

        int bad = 0;
        for (int i = 0; i < count; ++i)
            if (arr[i] > k)
                ++bad;

        int ans = bad;
        for (int i = 0, j = count; j < n; ++i, ++j)
        {

            if (arr[i] > k)
                --bad;

            if (arr[j] > k)
                ++bad;

            ans = Math.min(ans, bad);
        }
        return ans;
    }
    public static void main(String[] args)
    {
        int arr[] = {4,6,1,3,2};
        int n = arr.length;
        int k = 4;
        int result = minimumSwapToK(arr, n, k);
        System.out.println(result);

    }
}

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 중첩 루프가없는 실행 루프가 있었기 때문입니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

O (1) 추가 공간이 필요하지 않습니다. 따라서 공간 복잡성은 일정합니다.