最多k次交换后的最大置换-yiteyi-C++库

给出了第一个 N 作为数组和整数的自然数 K .打印最多后按字典顺序排列的最大排列 K 交换

null

例如：

Input: arr[] = {4, 5, 2, 1, 3}       k = 3Output: 5 4 3 2 1Swap 1^st and 2^nd elements: 5 4 2 1 3 Swap 3^rd and 5^th elements: 5 4 3 1 2 Swap 4^th and 5^th elements: 5 4 3 2 1 Input: arr[] = {2, 1, 3}       k = 1Output: 3 1 2Swap 1^st and 3^re elements: 3 1 2

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

天真的方法 : 其思想是按照字典顺序递减的顺序一个接一个地生成排列。将生成的每个置换与原始数组进行比较，然后计算转换所需的掉期数量 .如果计数小于或等于k，则打印此排列。这种方法的问题是，它很难实现，而且对于N的大值，它肯定会超时。

算法：

找到将一个数组转换为另一个数组的最小交换数这文章
复制原始数组并按降序排序。所以排序数组是原始数组的最大排列。
现在按字典顺序降序生成所有排列。之前的排列是使用 prev_置换（） 作用
如果计数小于或等于k，则找到将新数组（按降序排列）转换为原始数组所需的最小步骤。然后打印数组并断开。

C++14

                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function returns the minimum number                       
                         // of swaps required to sort the array                       
                         // This method is taken from below post                       
                         //                           https://                          www.geeksforgeeks.org/                       
                         // minimum-number-swaps-required-sort-array/                       
                         int                                     minSwapsToSort(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // Create an array of pairs where first                       
                                                 // element is array element and second                       
                                                 // element is position of first element                       
                                                 pair<                                     int                                     ,                                     int                                     > arrPos[n];                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 arrPos[i].first = arr[i];                       
                                                 arrPos[i].second = i;                       
                                                 }                       
           
                                                 // Sort the array by array element                       
                                                 // values to get right position of                       
                                                 // every element as second                       
                                                 // element of pair.                       
                                                 sort(arrPos, arrPos + n);                       
           
                                                 // To keep track of visited elements.                       
                                                 // Initialize all elements as not                       
                                                 // visited or false.                       
                                                 vector<                                     bool                                     > vis(n,                                     false                                     );                       
           
                                                 // Initialize result                       
                                                 int                                     ans = 0;                       
           
                                                 // Traverse array elements                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 // Already swapped and corrected or                       
                                                 // already present at correct pos                       
                                                 if                                     (vis[i] || arrPos[i].second == i)                       
                                                 continue                                     ;                       
           
                                                 // Find out the number of  node in                       
                                                 // this cycle and add in ans                       
                                                 int                                     cycle_size = 0;                       
                                                 int                                     j = i;                       
                                                 while                                     (!vis[j]) {                       
                                                 vis[j] = 1;                       
           
                                                 // move to next node                       
                                                 j = arrPos[j].second;                       
                                                 cycle_size++;                       
                                                 }                       
           
                                                 // Update answer by adding current                       
                                                 // cycle.                       
                                                 ans += (cycle_size - 1);                       
                                                 }                       
           
                                                 // Return result                       
                                                 return                                     ans;                       
                         }                       
           
                         // method returns minimum number of                       
                         // swap to make array B same as array A                       
                         int                                     minSwapToMakeArraySame(                       
                                                 int                                     a[],                                     int                                     b[],                                     int                                     n)                       
                         {                       
                                                 // Map to store position of elements                       
                                                 // in array B we basically store                       
                                                 // element to index mapping.                       
                                                 map<                                     int                                     ,                                     int                                     > mp;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 mp[b[i]] = i;                       
           
                                                 // now we're storing position of array                       
                                                 // A elements in array B.                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 b[i] = mp[a[i]];                       
           
                                                 /* We can uncomment this section to                       
                                                 print modified b array                       
                                                 for (int i = 0; i < N; i++)                       
                                                 cout << b[i] << " ";                       
                                                 cout << endl; */                       
           
                                                 // Returning minimum swap for sorting                       
                                                 // in modified array B as final answer                       
                                                 return                                     minSwapsToSort(b, n);                       
                         }                       
           
                         // Function to calculate largest                       
                         // permutation after atmost K swaps                       
                         void                                     KswapPermutation(                       
                                                 int                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     a[n];                       
           
                                                 // copy the array                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 a[i] = arr[i];                       
           
                                                 // Sort the array in descending order                       
                                                 sort(arr, arr + n, greater<                                     int                                     >());                       
           
                                                 // generate permutation in lexicographically                       
                                                 // decreasing order.                       
                                                 do                                     {                       
                                                 // copy the array                       
                                                 int                                     a1[n], b1[n];                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 a1[i] = arr[i];                       
                                                 b1[i] = a[i];                       
                                                 }                       
           
                                                 // Check if it can be made same in k steps                       
                                                 if                                     (                       
                                                 minSwapToMakeArraySame(                       
                                                 a1, b1, n)                       
                                                 <= k) {                       
                                                 // Print the array                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
                                                 break                                     ;                       
                                                 }                       
           
                                                 // move to previous permutation                       
                                                 }                                     while                                     (prev_permutation(arr, arr + n));                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 4, 5, 2, 1, 3 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 int                                     k = 3;                       
           
                                                 cout <<                                     "Largest permutation after "                       
                                                 << k <<                                     " swaps:"                                     ;                       
           
                                                 KswapPermutation(arr, n, k);                       
                                                 return                                     0;                       
                         }                       

输出

Largest permutation after 3 swaps:5 4 3 2 1

复杂性分析：

时间复杂性： O（N！）。生成所有置换O（N！）时间复杂性是必需的。
空间复杂性： O（n）。要存储新阵列，需要O（n）空间。

另一个值得考虑的方法是：

这个问题可以看作是“受控”选择排序的一个例子。所谓受控，我们的意思是我们没有对整个数组执行选择排序操作。相反，我们将自己构建为只允许我们执行的交换总数K。

所以在下面的方法中，我们所需要做的只是让选择排序进行k次，而不是更多。此外，我们需要检查我们将要与当前位置i交换的最大数量的位置是否等于该位置中已经存在的数量，我们需要跳过这个特殊情况，以免浪费我们有限的交换数量。

C++14

                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         void                                     KswapPermutation(                       
                                                 int                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 for                                     (                                     int                                     i=0;i<n-1;i++)                       
                                                 {                       
                                                 if                                     ( k>0)                       
                                                 {                       
                                                 int                                     max = i;                       
                                                 for                                     (                                     int                                     j=i+1;j<n;j++)                       
                                                 if                                     (arr[j]>arr[max])                       
                                                 max = j;                       
                                   
                                                 // this condition checks whether the max value has changed since when                       
                                                 // we started , or is it the same.                       
                                                 // We need to ignore the swap if the value is same.                       
                                                 // It means that the number ought to be present at the ith position , is already                       
                                                 // there.                       
                                                 if                                     (max!=i)                       
                                                 {                       
                                                 int                                     temp = arr[max];                       
                                                 arr[max] = arr[i];                       
                                                 arr[i] = temp;                       
                                                 k--;                       
                                                 }                       
                                                 }                       
                                                 else                       
                                                 break                                     ;                       
                                                 }                       
                         }                       
                                   
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 4, 5, 2, 1, 3 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 int                                     k = 3;                       
                                                 KswapPermutation(arr, n, k);                       
                                                 cout <<                                     "Largest permutation after "                       
                                                 << k <<                                     " swaps:"                                     <<endl;                       
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 cout<<arr[i]<<                                     " "                                     ;                       
                                                 return                                     0;                       
                         }                       

Python3

                         def                                     KswapPermutation(arr, n, k):                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n                                     -                                     1                                     ):                       
                                                 if                                     (k >                                     0                                     ):                       
                                                 max                                     =                                     i                       
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     , n):                       
                                                 if                                     (arr[j] > arr[                                     max                                     ]):                       
                                                 max                                     =                                     j                       
           
                                                 # this condition checks whether the max value has changed since when                       
                                                 # we started , or is it the same.                       
                                                 # We need to ignore the swap if the value is same.                       
                                                 # It means that the number ought to be present at the ith position , is already                       
                                                 # there.                       
                                                 if                                     (                                     max                                     !                                     =                                     i):                       
                                                 temp                                     =                                     arr[                                     max                                     ]                       
                                                 arr[                                     max                                     ]                                     =                                     arr[i]                       
                                                 arr[i]                                     =                                     temp                       
                                                 k                                     =                                     k                                     -                                     1                       
           
                                                 else                                     :                       
                                                 break                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     1                                     ,                                     3                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         k                                     =                                     3                       
                         KswapPermutation(arr, n, k)                       
                         print                                     (                                     "Largest permutation after "                                     +                                     str                                     (k)                                     +                                     " swaps:"                                     )                       
                         for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
                                                 print                                     (arr[i], end                                     =                                     ' '                                     )                       
           
                         # This code is contributed by Harsh Khatri                       

输出

Largest permutation after 3 swaps:5 4 3 2 1

复杂性分析 :

时间复杂性 ：O（n^2），因为这种方法使用选择排序
空间复杂性 ：O（1），因为分拣已就位，不需要额外的空间

有效的方法 : 这是一种贪婪的做法。当最大的元素位于数组的前面时，即最大的元素按降序排序时，会发现最大的排列。最多有k个掉期，所以把1 ^圣 2. ^钕 3. ^研发部，…，k ^th 最大的元素位于各自的位置。

注：如果允许的交换数量等于数组的大小，则无需迭代整个数组。答案就是反向排序数组。

算法：

创建一个HashMap或长度为n的数组来存储元素索引对或将元素映射到其索引。
现在循环k次。
在每次迭代中，将第i个元素与元素n–i交换。其中i是循环的索引或计数。还可以交换它们的位置，即更新hashmap或数组。所以在这一步中，剩余元素中最大的元素被交换到前面。
打印输出数组。

实施1： 这使用简单的数组来获得解决方案。

C++

                         // Below is C++ code to print largest                       
                         // permutation after at most K swaps                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to calculate largest                       
                         // permutation after atmost K swaps                       
                         void                                     KswapPermutation(                       
                                                 int                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 // Auxiliary dictionary of                       
                                                 // storing the position of elements                       
                                                 int                                     pos[n + 1];                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 pos[arr[i]] = i;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n && k; ++i) {                       
                                                 // If element is already i'th largest,                       
                                                 // then no need to swap                       
                                                 if                                     (arr[i] == n - i)                       
                                                 continue                                     ;                       
           
                                                 // Find position of i'th                       
                                                 // largest value, n-i                       
                                                 int                                     temp = pos[n - i];                       
           
                                                 // Swap the elements position                       
                                                 pos[arr[i]] = pos[n - i];                       
                                                 pos[n - i] = i;                       
           
                                                 // Swap the ith largest value with the                       
                                                 // current value at ith place                       
                                                 swap(arr[temp], arr[i]);                       
           
                                                 // decrement number of swaps                       
                                                 --k;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 4, 5, 2, 1, 3 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 int                                     k = 3;                       
           
                                                 KswapPermutation(arr, n, k);                       
                                                 cout <<                                     "Largest permutation after "                       
                                                 << k <<                                     " swaps:n"                                     ;                       
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 printf                                     (                                     "%d "                                     , arr[i]);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Below is Java code to print                       
                         // largest permutation after                       
                         // atmost K swaps                       
                         class                                     GFG {                       
           
                                                 // Function to calculate largest                       
                                                 // permutation after atmost K swaps                       
                                                 static                                     void                                     KswapPermutation(                       
                                                 int                                     arr[],                                     int                                     n,                                     int                                     k)                       
                                                 {                       
           
                                                 // Auxiliary dictionary of storing                       
                                                 // the position of elements                       
                                                 int                                     pos[] =                                     new                                     int                                     [n +                                     1                                     ];                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; ++i)                       
                                                 pos[arr[i]] = i;                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n && k >                                     0                                     ; ++i) {                       
           
                                                 // If element is already i'th                       
                                                 // largest, then no need to swap                       
                                                 if                                     (arr[i] == n - i)                       
                                                 continue                                     ;                       
           
                                                 // Find position of i'th largest                       
                                                 // value, n-i                       
                                                 int                                     temp = pos[n - i];                       
           
                                                 // Swap the elements position                       
                                                 pos[arr[i]] = pos[n - i];                       
                                                 pos[n - i] = i;                       
           
                                                 // Swap the ith largest value with the                       
                                                 // current value at ith place                       
                                                 int                                     tmp1 = arr[temp];                       
                                                 arr[temp] = arr[i];                       
                                                 arr[i] = tmp1;                       
           
                                                 // decrement number of swaps                       
                                                 --k;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
           
                                                 int                                     arr[] = {                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     1                                     ,                                     3                                     };                       
                                                 int                                     n = arr.length;                       
                                                 int                                     k =                                     3                                     ;                       
           
                                                 KswapPermutation(arr, n, k);                       
           
                                                 System.out.print(                       
                                                 "Largest permutation "                       
                                                 +                                     "after "                                     + k +                                     " swaps:"                                     );                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; ++i)                       
                                                 System.out.print(arr[i] +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python code to print largest permutation after K swaps                       
           
                         def                                     KswapPermutation(arr, n, k):                       
           
                                                 # Auxiliary array of storing the position of elements                       
                                                 pos                                     =                                     {}                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 pos[arr[i]]                                     =                                     i                       
           
                                                 for                                     i                                     in                                     range                                     (n):                       
           
                                                 # If K is exhausted then break the loop                       
                                                 if                                     k                                     =                                     =                                     0                                     :                       
                                                 break                       
           
                                                 # If element is already largest then no need to swap                       
                                                 if                                     (arr[i]                                     =                                     =                                     n                                     -                                     i):                       
                                                 continue                       
           
                                                 # Find position of i'th largest value, n-i                       
                                                 temp                                     =                                     pos[n                                     -                                     i]                       
           
                                                 # Swap the elements position                       
                                                 pos[arr[i]]                                     =                                     pos[n                                     -                                     i]                       
                                                 pos[n                                     -                                     i]                                     =                                     i                       
           
                                                 # Swap the ith largest value with the value at                       
                                                 # ith place                       
                                                 arr[temp], arr[i]                                     =                                     arr[i], arr[temp]                       
           
                                                 # Decrement K after swap                       
                                                 k                                     =                                     k                                     -                                     1                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     1                                     ,                                     3                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         k                                     =                                     3                       
                         KswapPermutation(arr, n, k)                       
           
                         # Print the answer                       
                         print                                     (                                     "Largest permutation after"                                     , k,                                     "swaps: "                                     )                       
                         print                                     (                                     " "                                     .join(                                     map                                     (                                     str                                     , arr)))                       

C#

                         // Below is C# code to print largest                       
                         // permutation after atmost K swaps.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Function to calculate largest                       
                                                 // permutation after atmost K                       
                                                 // swaps                       
                                                 static                                     void                                     KswapPermutation(                                     int                                     [] arr,                       
                                                 int                                     n,                                     int                                     k)                       
                                                 {                       
           
                                                 // Auxiliary dictionary of storing                       
                                                 // the position of elements                       
                                                 int                                     [] pos =                                     new                                     int                                     [n + 1];                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 pos[arr[i]] = i;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n && k > 0; ++i) {                       
           
                                                 // If element is already i'th                       
                                                 // largest, then no need to swap                       
                                                 if                                     (arr[i] == n - i)                       
                                                 continue                                     ;                       
           
                                                 // Find position of i'th largest                       
                                                 // value, n-i                       
                                                 int                                     temp = pos[n - i];                       
           
                                                 // Swap the elements position                       
                                                 pos[arr[i]] = pos[n - i];                       
                                                 pos[n - i] = i;                       
           
                                                 // Swap the ith largest value with                       
                                                 // the current value at ith place                       
                                                 int                                     tmp1 = arr[temp];                       
                                                 arr[temp] = arr[i];                       
                                                 arr[i] = tmp1;                       
           
                                                 // decrement number of swaps                       
                                                 --k;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
           
                                                 int                                     [] arr = { 4, 5, 2, 1, 3 };                       
                                                 int                                     n = arr.Length;                       
                                                 int                                     k = 3;                       
           
                                                 KswapPermutation(arr, n, k);                       
           
                                                 Console.Write(                                     "Largest permutation "                       
                                                 +                                     "after "                                     + k +                                     " swaps:"                                     );                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed nitin mittal.                       

PHP

                         <?php                       
                         // PHP code to print largest permutation                       
                         // after atmost K swaps                       
           
                         // Function to calculate largest                       
                         // permutation after atmost K swaps                       
                         function                                     KswapPermutation(&                                     $arr                                     ,                                     $n                                     ,                                     $k                                     )                       
                         {                       
           
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ; ++                                     $i                                     )                       
                                                 $pos                                     [                                     $arr                                     [                                     $i                                     ]] =                                     $i                                     ;                       
           
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     &&                                     $k                                     ; ++                                     $i                                     )                       
                                                 {                       
                                                 // If element is already i'th largest,                       
                                                 // then no need to swap                       
                                                 if                                     (                                     $arr                                     [                                     $i                                     ] ==                                     $n                                     -                                     $i                                     )                       
                                                 continue                                     ;                       
           
                                                 // Find position of i'th largest                       
                                                 // value, n-i                       
                                                 $temp                                     =                                     $pos                                     [                                     $n                                     -                                     $i                                     ];                       
           
                                                 // Swap the elements position                       
                                                 $pos                                     [                                     $arr                                     [                                     $i                                     ]] =                                     $pos                                     [                                     $n                                     -                                     $i                                     ];                       
                                                 $pos                                     [                                     $n                                     -                                     $i                                     ] =                                     $i                                     ;                       
           
                                                 // Swap the ith largest value with the                       
                                                 // current value at ith place                       
                                                 $t                                     =                                     $arr                                     [                                     $temp                                     ];                       
                                                 $arr                                     [                                     $temp                                     ] =                                     $arr                                     [                                     $i                                     ];                       
                                                 $arr                                     [                                     $i                                     ] =                                     $t                                     ;                       
                                   
                                                 // decrement number of swaps                       
                                                 --                                     $k                                     ;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         $arr                                     =                                     array                                     (4, 5, 2, 1, 3);                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         $k                                     = 3;                       
           
                         KswapPermutation(                                     $arr                                     ,                                     $n                                     ,                                     $k                                     );                       
                         echo                                     (                                     "Largest permutation after "                                     );                       
                         echo                                     (                                     $k                                     );                       
                         echo                                     (                                     " swaps:"                                     );                       
                         for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ; ++                                     $i                                     )                       
                         {                       
                                                 echo                                     (                                     $arr                                     [                                     $i                                     ] );                       
                                                 echo                                     (                                     " "                                     );                       
                         }                       
           
                         // This code is contributed                       
                         // by Shivi_Aggarwal                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // Below is Javascript code to print largest                       
                                                 // permutation after at most K swaps                       
                                   
                                                 // Function to calculate largest                       
                                                 // permutation after atmost K swaps                       
                                                 function                                     KswapPermutation(arr, n, k)                       
                                                 {                       
                                                 // Auxiliary dictionary of                       
                                                 // storing the position of elements                       
                                                 let pos =                                     new                                     Array(n + 1);                       
           
                                                 for                                     (let i = 0; i < n; ++i)                       
                                                 pos[arr[i]] = i;                       
           
                                                 for                                     (let i = 0; i < n && k; ++i) {                       
                                                 // If element is already i'th largest,                       
                                                 // then no need to swap                       
                                                 if                                     (arr[i] == n - i)                       
                                                 continue                                     ;                       
           
                                                 // Find position of i'th                       
                                                 // largest value, n-i                       
                                                 let temp = pos[n - i];                       
           
                                                 // Swap the elements position                       
                                                 pos[arr[i]] = pos[n - i];                       
                                                 pos[n - i] = i;                       
           
                                                 // Swap the ith largest value with the                       
                                                 // current value at ith place                       
                                                 let tmp1 = arr[temp];                       
                                                 arr[temp] = arr[i];                       
                                                 arr[i] = tmp1;                       
           
                                                 // decrement number of swaps                       
                                                 --k;                       
                                                 }                       
                                                 }                       
           
                                                 let arr = [ 4, 5, 2, 1, 3 ];                       
                                                 let n = arr.length;                       
                                                 let k = 3;                       
                                   
                                                 KswapPermutation(arr, n, k);                       
                                                 document.write(                                     "Largest permutation after "                                     + k +                                     " swaps:"                                     +                                     "</br>"                                     );                       
                                                 for                                     (let i = 0; i < n; ++i)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
                                   
                         </script>                       

输出

Largest permutation after 3 swaps:n5 4 3 2 1

输出：

Largest permutation after 3 swaps:5 4 3 2 1

实施2： 这将使用hashmap来获得解决方案。

C++

                         // C++ Program to find the                       
                         // largest permutation after                       
                         // at most k swaps using unordered_map.                       
                         #include <bits/stdc++.h>                       
                         #include <unordered_map>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find the largest                       
                         // permutation after k swaps                       
                         void                                     bestpermutation(                       
                                                 int                                     arr[],                                     int                                     k,                                     int                                     n)                       
                         {                       
                                                 // Storing the elements and                       
                                                 // their index in map                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > h;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 h.insert(make_pair(arr[i], i));                       
                                                 }                       
           
                                                 // If number of swaps allowed                       
                                                 // are equal to number of elements                       
                                                 // then the resulting permutation                       
                                                 // will be descending order of                       
                                                 // given permutation.                       
                                                 if                                     (n <= k) {                       
                                                 sort(arr, arr + n, greater<                                     int                                     >());                       
                                                 }                       
                                                 else                                     {                       
           
                                                 for                                     (                                     int                                     j = n; j >= 1; j--) {                       
                                                 if                                     (k > 0) {                       
           
                                                 int                                     initial_index = h[j];                       
                                                 int                                     best_index = n - j;                       
           
                                                 // if j is not at it's best index                       
                                                 if                                     (initial_index != best_index) {                       
           
                                                 h[j] = best_index;                       
           
                                                 // Change the index of the element                       
                                                 // which was at position 0. Swap                       
                                                 // the element basically.                       
                                                 int                                     element = arr[best_index];                       
                                                 h[element] = initial_index;                       
                                                 swap(                       
                                                 arr[best_index],                       
                                                 arr[initial_index]);                       
           
                                                 // decrement number of swaps                       
                                                 k--;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 3, 1, 4, 2, 5 };                       
           
                                                 // K is the number of swaps                       
                                                 int                                     k = 10;                       
           
                                                 // n is the size of the array                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (                                     int                                     );                       
           
                                                 // Function calling                       
                                                 bestpermutation(arr, k, n);                       
           
                                                 cout <<                                     "Largest possible permutation after "                       
                                                 << k <<                                     " swaps is "                                     ;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
           
                                                 return                                     0;                       
                         }                       
                         // This method is contributed by Kishan Mishra.                       

JAVA

                         // Java Program to find the                       
                         // largest permutation after                       
                         // at most k swaps using unordered_map.                       
                         import                                     java.util.*;                       
                         class                                     GFG                       
                         {                       
           
                                                 // Function to find the largest                       
                                                 // permutation after k swaps                       
                                                 static                                     void                                     bestpermutation(ArrayList<Integer> arr,                                     int                                     k,                                     int                                     n)                       
                                                 {                       
           
                                                 // Storing the elements and                       
                                                 // their index in map                       
                                                 HashMap<Integer, Integer> h =                       
                                                 new                                     HashMap<Integer, Integer>();                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 h.put(arr.get(i), i);                       
                                                 }                       
           
                                                 // If number of swaps allowed                       
                                                 // are equal to number of elements                       
                                                 // then the resulting permutation                       
                                                 // will be descending order of                       
                                                 // given permutation.                       
                                                 if                                     (n <= k) {                       
                                                 Collections.sort(arr, Collections.reverseOrder());                       
                                                 }                       
                                                 else                                     {                       
           
                                                 for                                     (                                     int                                     j = n; j >=                                     1                                     ; j--)                       
                                                 {                       
                                                 if                                     (k >                                     0                                     )                       
                                                 {                       
           
                                                 int                                     initial_index = h.get(j);                       
                                                 int                                     best_index = n - j;                       
           
                                                 // if j is not at it's best index                       
                                                 if                                     (initial_index != best_index)                       
                                                 {                       
                                                 h.put(j, best_index);                       
           
                                                 // Change the index of the element                       
                                                 // which was at position 0. Swap                       
                                                 // the element basically.                       
                                                 int                                     element = arr.get(best_index);                       
                                                 h.put(element, initial_index);                       
                                                 int                                     temp = arr.get(best_index);                       
                                                 arr.set(best_index, arr.get(initial_index));                       
                                                 arr.set(initial_index, temp);                       
           
                                                 // decrement number of swaps                       
                                                 k--;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String []args)                       
                                                 {                       
           
                                                 ArrayList<Integer> arr =                                     new                                     ArrayList<Integer>();                       
                                                 arr.add(                                     3                                     );                       
                                                 arr.add(                                     1                                     );                       
                                                 arr.add(                                     4                                     );                       
                                                 arr.add(                                     2                                     );                       
                                                 arr.add(                                     5                                     );                       
           
                                                 // K is the number of swaps                       
                                                 int                                     k =                                     10                                     ;                       
           
                                                 // n is the size of the array                       
                                                 int                                     n = arr.size();                       
           
                                                 // Function calling                       
                                                 bestpermutation(arr, k, n);                       
           
                                                 System.out.print(                                     "Largest possible permutation after "                                     + k +                                     " swaps is "                                     );                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 System.out.print(arr.get(i) +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by rutvik_56.                       

Python3

                         # Python3 program to find the                       
                         # largest permutation after                       
                         # at most k swaps using unordered_map.                       
           
                         # Function to find the largest                       
                         # permutation after k swaps                       
                         def                                     bestpermutation(arr, k, n):                       
                                   
                                                 # Storing the elements and                       
                                                 # their index in map                       
                                                 h                                     =                                     {}                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 h[arr[i]]                                     =                                     i                       
           
                                                 # If number of swaps allowed                       
                                                 # are equal to number of elements                       
                                                 # then the resulting permutation                       
                                                 # will be descending order of                       
                                                 # given permutation.                       
                                                 if                                     (n <                                     =                                     k):                       
                                                 arr.sort()                       
                                                 arr.reverse()                       
                                                 else                                     :                       
                                   
                                                 for                                     j                                     in                                     range                                     (n,                                     0                                     ,                                     -                                     1                                     ):                       
                                                 if                                     (k >                                     0                                     ):                       
                                                 initial_index                                     =                                     h[j]                       
                                                 best_index                                     =                                     n                                     -                                     j                       
           
                                                 # If j is not at it's best index                       
                                                 if                                     (initial_index !                                     =                                     best_index):                       
                                                 h[j]                                     =                                     best_index                       
           
                                                 # Change the index of the element                       
                                                 # which was at position 0. Swap                       
                                                 # the element basically.                       
                                                 element                                     =                                     arr[best_index]                       
                                                 h[element]                                     =                                     initial_index                       
                                                 arr[best_index], arr[initial_index]                                     =                                     (arr[initial_index],                       
                                                 arr[best_index])                       
                                   
                                                 # Decrement number of swaps                       
                                                 k                                     -                                     =                                     1                       
           
                         # Driver Code                       
                         arr                                     =                                     [                                     3                                     ,                                     1                                     ,                                     4                                     ,                                     2                                     ,                                     5                                     ]                       
           
                         # K is the number of swaps                       
                         k                                     =                                     10                       
           
                         # n is the size of the array                       
                         n                                     =                                     len                                     (arr)                       
           
                         # Function calling                       
                         bestpermutation(arr, k, n)                       
           
                         print                                     (                                     "Largest possible permutation after"                                     ,                       
                                                 k,                                     "swaps is"                                     , end                                     =                                     " "                                     )                       
                                   
                         for                                     i                                     in                                     range                                     (n):                       
                                                 print                                     (arr[i], end                                     =                                     " "                                     )                       
           
                         # This code is contributed by divyesh072019                       

C#

                         // C# Program to find the                       
                         // largest permutation after                       
                         // at most k swaps using unordered_map.                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                         class                                     GFG {                       
                                   
                                                 // Function to find the largest                       
                                                 // permutation after k swaps                       
                                                 static                                     void                                     bestpermutation(List<                                     int                                     > arr,                                     int                                     k,                                     int                                     n)                       
                                                 {                       
                                                 // Storing the elements and                       
                                                 // their index in map                       
                                                 Dictionary<                                     int                                     ,                                     int                                     > h =                       
                                                 new                                     Dictionary<                                     int                                     ,                                     int                                     >();                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 h.Add(arr[i], i);                       
                                                 }                       
                                   
                                                 // If number of swaps allowed                       
                                                 // are equal to number of elements                       
                                                 // then the resulting permutation                       
                                                 // will be descending order of                       
                                                 // given permutation.                       
                                                 if                                     (n <= k) {                       
                                                 arr.Sort();                       
                                                 arr.Reverse();                       
                                                 }                       
                                                 else                                     {                       
                                   
                                                 for                                     (                                     int                                     j = n; j >= 1; j--) {                       
                                                 if                                     (k > 0) {                       
                                   
                                                 int                                     initial_index = h[j];                       
                                                 int                                     best_index = n - j;                       
                                   
                                                 // if j is not at it's best index                       
                                                 if                                     (initial_index != best_index) {                       
                                   
                                                 h[j] = best_index;                       
                                   
                                                 // Change the index of the element                       
                                                 // which was at position 0. Swap                       
                                                 // the element basically.                       
                                                 int                                     element = arr[best_index];                       
                                                 h[element] = initial_index;                       
                                                 int                                     temp = arr[best_index];                       
                                                 arr[best_index] = arr[initial_index];                       
                                                 arr[initial_index] = temp;                       
                                   
                                                 // decrement number of swaps                       
                                                 k--;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 static                                     void                                     Main() {                       
                                                 List<                                     int                                     > arr =                                     new                                     List<                                     int                                     >(                                     new                                     int                                     [] {3, 1, 4, 2, 5 });                       
                                   
                                                 // K is the number of swaps                       
                                                 int                                     k = 10;                       
                                   
                                                 // n is the size of the array                       
                                                 int                                     n = arr.Count;                       
                                   
                                                 // Function calling                       
                                                 bestpermutation(arr, k, n);                       
                                   
                                                 Console.Write(                                     "Largest possible permutation after "                                     + k +                                     " swaps is "                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by divyeshrabadiya07                       

Javascript

                         <script>                       
           
                         // JavaScript Program to find the                       
                         // largest permutation after                       
                         // at most k swaps using unordered_map.                       
           
                         // Function to find the largest                       
                                                 // permutation after k swaps                       
                         function                                     bestpermutation(arr,k,n)                       
                         {                       
                                                 // Storing the elements and                       
                                                 // their index in map                       
                                                 let h =                       
                                                 new                                     Map();                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 h.set(arr[i], i);                       
                                                 }                       
                                   
                                                 // If number of swaps allowed                       
                                                 // are equal to number of elements                       
                                                 // then the resulting permutation                       
                                                 // will be descending order of                       
                                                 // given permutation.                       
                                                 if                                     (n <= k) {                       
                                                 arr.sort(                                     function                                     (a,b){                                     return                                     b-a;});                       
                                                 }                       
                                                 else                                     {                       
                                   
                                                 for                                     (let j = n; j >= 1; j--)                       
                                                 {                       
                                                 if                                     (k > 0)                       
                                                 {                       
                                   
                                                 let initial_index = h[j];                       
                                                 let best_index = n - j;                       
                                   
                                                 // if j is not at it's best index                       
                                                 if                                     (initial_index != best_index)                       
                                                 {                       
                                                 h.set(j, best_index);                       
                                   
                                                 // Change the index of the element                       
                                                 // which was at position 0. Swap                       
                                                 // the element basically.                       
                                                 let element = arr.get(best_index);                       
                                                 h.set(element, initial_index);                       
                                                 let temp = arr[best_index];                       
                                                 arr.set(best_index, arr[initial_index]);                       
                                                 arr.set(initial_index, temp);                       
                                   
                                                 // decrement number of swaps                       
                                                 k--;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         let arr=[3,1,4,2,5];                       
                         // K is the number of swaps                       
                         let k = 10;                       
           
                         // n is the size of the array                       
                         let n = arr.length;                       
           
                         // Function calling                       
                         bestpermutation(arr, k, n);                       
           
                         document.write(                       
                         "Largest possible permutation after "                                     + k +                                     " swaps is "                       
                         );                       
           
                         for                                     (let i = 0; i < n; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
           
           
                         // This code is contributed by avanitrachhadiya2155                       
           
                         </script>                       

输出

Largest possible permutation after 10 swaps is 5 4 3 2 1

输出：

Largest possible permutation after 10 swaps is 5 4 3 2 1

复杂性分析：

时间复杂性： O（N）。只需要遍历数组一次。
空间复杂性： O（n）。要存储新阵列，需要O（n）空间。

本文由 Shubham Bansal .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章