# 算法：将所有小于或等于k的元素组合在一起所需的最小交换

2021年3月29日18:04:36 发表评论 385 次浏览

## 本文概述

``````Input:  arr[] = {2, 1, 5, 6, 3}, k = 3
Output: 1

Explanation:
To bring elements 2, 1, 3 together, swap
element '5' with '3' such that final array
will be-
arr[] = {2, 1, 3, 6, 5}

Input:  arr[] = {2, 7, 9, 5, 8, 7, 4}, k = 5
Output: 2``````

1）查找所有小于或等于" k"的元素的计数。假设计数是" cnt"

## C ++

``````// C++ program to find minimum swaps required
// to club all elements less than or equals
// to k together
#include <iostream>
using namespace std;

// Utility function to find minimum swaps
// required to club all elements less than
// or equals to k together
int minSwap( int *arr, int n, int k) {

// Find count of elements which are
// less than equals to k
int count = 0;
for ( int i = 0; i < n; ++i)
if (arr[i] <= k)
++count;

// Find unwanted elements in current
// window of size 'count'
for ( int i = 0; i < count; ++i)
if (arr[i] > k)

// current window
for ( int i = 0, j = count; j < n; ++i, ++j) {

// Decrement count of previous window
if (arr[i] > k)

// Increment count of current window
if (arr[j] > k)

// Update ans if count of 'bad'
// is less in current window
}
return ans;
}

// Driver code
int main() {

int arr[] = {2, 1, 5, 6, 3};
int n = sizeof (arr) / sizeof (arr[0]);
int k = 3;
cout << minSwap(arr, n, k) << "\n" ;

int arr1[] = {2, 7, 9, 5, 8, 7, 4};
n = sizeof (arr1) / sizeof (arr1[0]);
k = 5;
cout << minSwap(arr1, n, k);
return 0;
}``````

## Java

``````// Java program to find minimum
// swaps required to club all
// elements less than or equals
// to k together
import java.lang.*;

class GFG {

// Utility function to find minimum swaps
// required to club all elements less than
// or equals to k together
static int minSwap( int arr[], int n, int k) {

// Find count of elements which are
// less than equals to k
int count = 0 ;
for ( int i = 0 ; i < n; ++i)
if (arr[i] <= k)
++count;

// Find unwanted elements in current
// window of size 'count'
for ( int i = 0 ; i < count; ++i)
if (arr[i] > k)

// current window
for ( int i = 0 , j = count; j < n; ++i, ++j) {

// Decrement count of previous window
if (arr[i] > k)

// Increment count of current window
if (arr[j] > k)

// Update ans if count of 'bad'
// is less in current window
}
return ans;
}

// Driver code
public static void main(String[] args)
{
int arr[] = { 2 , 1 , 5 , 6 , 3 };
int n = arr.length;
int k = 3 ;
System.out.print(minSwap(arr, n, k) + "\n" );

int arr1[] = { 2 , 7 , 9 , 5 , 8 , 7 , 4 };
n = arr1.length;
k = 5 ;
System.out.print(minSwap(arr1, n, k));
}
}

// This code is contributed by Anant Agarwal.``````

## Python3

``````# Python3 program to find
# minimum swaps required
# to club all elements less
# than or equals to k together

# Utility function to find
# minimum swaps required to
# club all elements less than
# or equals to k together
def minSwap(arr, n, k) :

# Find count of elements
# which are less than
# equals to k
count = 0
for i in range ( 0 , n) :
if (arr[i] < = k) :
count = count + 1

# Find unwanted elements
# in current window of
# size 'count'
for i in range ( 0 , count) :
if (arr[i] > k) :

# window
j = count
for i in range ( 0 , n) :

if (j = = n) :
break

# Decrement count of
# previous window
if (arr[i] > k) :

# Increment count of
# current window
if (arr[j] > k) :

# Update ans if count
# of 'bad' is less in
# current window

j = j + 1

return ans

# Driver code
arr = [ 2 , 1 , 5 , 6 , 3 ]
n = len (arr)
k = 3
print (minSwap(arr, n, k))

arr1 = [ 2 , 7 , 9 , 5 , 8 , 7 , 4 ]
n = len (arr1)
k = 5
print (minSwap(arr1, n, k))

# This code is contributed by
# Manish Shaw(manishshaw1)``````

## C#

``````// C# program to find minimum
// swaps required to club all
// elements less than or equals
// to k together
using System;

class GFG {

// Utility function to find minimum swaps
// required to club all elements less than
// or equals to k together
static int minSwap( int []arr, int n, int k) {

// Find count of elements which are
// less than equals to k
int count = 0;
for ( int i = 0; i < n; ++i)
if (arr[i] <= k)
++count;

// Find unwanted elements in current
// window of size 'count'
for ( int i = 0; i < count; ++i)
if (arr[i] > k)

// current window
for ( int i = 0, j = count; j < n; ++i, ++j) {

// Decrement count of previous window
if (arr[i] > k)

// Increment count of current window
if (arr[j] > k)

// Update ans if count of 'bad'
// is less in current window
}
return ans;
}

// Driver code
public static void Main()
{
int []arr = {2, 1, 5, 6, 3};
int n = arr.Length;
int k = 3;
Console.WriteLine(minSwap(arr, n, k));

int []arr1 = {2, 7, 9, 5, 8, 7, 4};
n = arr1.Length;
k = 5;
Console.WriteLine(minSwap(arr1, n, k));
}
}

// This code is contributed by vt_m.``````

## 的PHP

``````<?php
// PHP program to find
// minimum swaps required
// to club all elements
// less than or equals
// to k together

// Utility function to
// find minimum swaps
// required to club all
// elements less than
// or equals to k together
function minSwap( \$arr , \$n , \$k )
{

// Find count of elements
// which are less than
// equals to k
\$count = 0;
for ( \$i = 0; \$i < \$n ; ++ \$i )
if ( \$arr [ \$i ] <= \$k )
++ \$count ;

// Find unwanted elements in current
// window of size 'count'
for ( \$i = 0; \$i < \$count ; ++ \$i )
if ( \$arr [ \$i ] > \$k )

// current window
for ( \$i = 0, \$j = \$count ; \$j < \$n ;
++ \$i , ++ \$j )
{

// Decrement count of
// previous window
if ( \$arr [ \$i ] > \$k )

// Increment count of
// current window
if ( \$arr [ \$j ] > \$k )

// Update ans if count of 'bad'
// is less in current window
\$ans = min( \$ans , \$bad );
}
return \$ans ;
}

// Driver code
\$arr = array (2, 1, 5, 6, 3);
\$n = sizeof( \$arr );
\$k = 3;
echo (minSwap( \$arr , \$n , \$k ) . "\n" );

\$arr1 = array (2, 7, 9, 5, 8, 7, 4);
\$n = sizeof( \$arr1 );
\$k = 5;
echo (minSwap( \$arr1 , \$n , \$k ));

// This code is contributed by Ajit.
?>``````

``````1
2``````