k보다 작거나 같은 모든 요소를 ​​결합하는 데 필요한 최소 스왑


난이도 쉽게
자주 묻는 질문 아마존 AppDynamics 팩트 셋 포카이트 Microsoft
배열

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

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

설명

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

암호알고리즘

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

설명

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

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

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

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

k보다 작거나 같은 모든 요소를 ​​결합하는 데 필요한 최소 스왑

암호

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;
}
1

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);

    }
}
1

복잡성 분석

시간 복잡성

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

공간 복잡성

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