本文概述
给定第一个的排列
ñ
自然数作为数组和整数
ķ
。在最多之后打印按字典顺序排列的最大排列
ķ
掉期
例子:
Input: arr[] = {4, 5, 2, 1, 3}
k = 3
Output: 5 4 3 2 1
Swap 1st and 2nd elements: 5 4 2 1 3
Swap 3rd and 5th elements: 5 4 3 1 2
Swap 4th and 5th elements: 5 4 3 2 1
Input: arr[] = {2, 1, 3}
k = 1
Output: 3 1 2
Swap 1st and 3re elements: 3 1 2
推荐:请在"实践首先, 在继续解决方案之前。
天真的方法:这个想法是按字典顺序递减的顺序生成一个排列。将每个生成的排列与原始数组进行比较, 然后计算转换所需的掉期数量。如果count小于或等于k, 则打印此排列。这种方法的问题在于难以实现, 并且肯定会因N的较大值而超时。
算法:
- 查找将一个数组转换为另一个数组的最小交换这个文章。
- 复制原始数组, 然后按降序对该数组排序。因此, 排序后的数组是原始数组的最大排列。
- 现在按字典顺序降序生成所有排列。先前的排列使用prev_permutation()功能。
- 如果计数小于或等于k, 则找到将新数组(降序排列)转换为原始数组所需的最小步骤。然后打印数组并中断。
#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.lsbin.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; */
// Returing 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:\n" ;
KswapPermutation(arr, n, k);
return 0;
}
输出如下:
Largest permutation after 3 swaps:
5 4 3 2 1
复杂度分析:
- 时间复杂度:上!)。
要生成所有置换O(N!), 需要时间复杂度。 - 空间复杂度:上)。
需要存储新数组O(n)空间。
高效的方法:这是一种贪婪的方法。当最大元素位于数组的前面时, 即找到最大排列时, 即最大元素按降序排序。最多有k个掉期, 因此将1st, 2nd, 3rd, …, kth在各自位置的最大元素。
注意:如果允许的交换数量等于数组的大小, 则无需遍历整个数组。答案将只是反向排序的数组。
算法:
- 创建一个HashMap或长度为n的数组, 以存储元素索引对或将元素映射到其索引。
- 现在运行一个循环k次。
- 在每次迭代中, 将第ith个元素与元素n – i交换。其中, i是循环的索引或计数。还要交换其位置, 即更新哈希图或数组。因此, 在此步骤中, 将剩余元素中的最大元素交换到最前面。
- 打印输出数组。
实施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:\n" );
for ( int i = 0 ; i < n; ++i)
System.out.print(arr[i] + " " );
}
}
// This code is contributed by Anant Agarwal.
python
# 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:\n" );
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:\n" );
for ( $i = 0; $i < $n ; ++ $i )
{
echo ( $arr [ $i ] );
echo ( " " );
}
// This code is contributed
// by Shivi_Aggarwal
?>
输出如下:
Largest permutation after 3 swaps:
5 4 3 2 1
实施2:这使用哈希图来得出解决方案。
// 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.
输出如下:
Largest possible permutation after 3 swaps is 5 4 3 2 1
复杂度分析:
- 时间复杂度:上)。
只需要遍历数组一次。 - 空间复杂度:上)。
要存储新数组, 需要O(n)空间。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。