C++에서 k보다 작거나 같은 모든 요소를 ​​함께 가져오는 데 필요한 최소 스왑

문제 설명

n개의 양의 정수와 숫자 k의 배열이 주어집니다. k보다 작거나 같은 모든 숫자를 모으는 데 필요한 최소 스왑 수를 찾으십시오.

예시

입력 배열이 {1, 5, 4, 7, 2, 10}이고 k =6이면 1개의 스왑이 필요합니다. 즉, 요소 ​​7을 2로 스왑합니다.

알고리즘

• 'k'보다 작거나 같은 모든 요소를 ​​센다. 개수가 'cnt'라고 가정해 보겠습니다.
• 길이가 'cnt'인 창에 대해 두 포인터 기술을 사용하여 매번 이 범위의 요소가 'k'보다 큰 수를 추적합니다. 총 개수가 'outOfRange'라고 가정해 보겠습니다.
• 길이가 'cnt'인 모든 창에 대해 2단계를 반복하고 그 중에서 최소 'outOfRange' 개수를 취합니다. 이것이 최종 답변이 될 것입니다.

예시

#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n, int k) {
   int cnt = 0;
   for (int i = 0; i < n; ++i) {
      if (arr[i] <= k) {
         ++cnt;
      }
   }
   int outOfRange = 0;
   for (int i = 0; i < cnt; ++i) {
      if (arr[i] > k) {
         ++outOfRange;
      }
   }
   int result = outOfRange;
   for (int i = 0, j = cnt; j < n; ++i, ++j) {
      if (arr[i] > k) {
         --outOfRange;
      }
      if (arr[j] > k) {
         ++outOfRange;
      }
      result = min(result, outOfRange);
   }
   return result;
}
int main() {
   int arr[] = {1, 5, 4, 7, 2, 10};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 6;
   cout << "Minimum swaps = " << getMinSwaps(arr, n, k) <<
   endl;
   return 0;
}

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

출력

Minimum swaps = 1