We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Greedy
- Largest Permutation
- Discussions
Largest Permutation
Largest Permutation
+ 25 comments There is an important part of the task that I missed: "permutation of the first N natural numbers"
+ 6 comments Here are few test cases to further help understand the problem: (as the provided test cases do not cover K > 1)
- Test Case 1
Input: 5 2 4 3 2 5 1 Intermediate: After first swap (of 5 and 4): 5 3 2 4 1 After second swap (of 3 and 4): 5 4 2 3 1 Output: 5 4 2 3 1
- Test Case 2
Input: 5 2 3 4 2 5 1 Intermediate: After first swap (of 5 and 3): 5 4 2 3 1 After second swap (of 2 and 3): 5 4 3 2 1 Output: 5 4 3 2 1
+ 18 comments Jave O(k) using index array
public class Solution {
public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); int k = input.nextInt(); int[] a = new int[n]; int[] index = new int[n + 1]; for (int i = 0; i < n; i++) { a[i] = input.nextInt(); index[a[i]] = i; } for (int i = 0; i < n && k > 0; i++) { if (a[i] == n - i) { continue; } a[index[n - i]] = a[i]; index[a[i]] = index[n - i]; a[i] = n - i; index[n - i] = i; k--; } for (int i = 0; i < n; i++) { System.out.print(a[i] + " "); } }
}
+ 4 comments c++ it works
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); long long int n,k,flag=0; cin>>n>>k; long long int i,j=0,arr[n],brr[n],temp; for(i=0;i<n;i++) { cin>>arr[i]; } for(i=0;i<n;i++) { if(arr[i]!=n-i&&k!=0) { j=i+1; while(arr[j]!=n-i) j++; temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; k--; } } for(i=0;i<n;i++) cout<<arr[i]<<" "; cout<<"\n"; return 0; }
+ 0 comments The success rate is only 60% for this problem. Don't know why it is marked "easy". I think this should be "medium"
Load more conversations
Sort 335 Discussions, By:
Please Login in order to post a comment