clean Java O(n*log n) solution with explaination


  • 0

    The problem is easy to understand:
    rearrange part/full of the array in a way that smallest in the front. Iterate from the end, find anything that is smaller than any already iterated element, if there is one, then rearrange from that element to the end. If not, rearrange the whole array.

    public class Solution {
        public void nextPermutation(int[] nums) {
            int n = nums.length, max = Integer.MIN_VALUE;
            Queue<Integer> q = new PriorityQueue<Integer>();
            for(int i = n-1;i >= 0; --i) {
                int cur = nums[i];
                q.add(cur);
                if(max > cur) {
                    reArrangeArray(nums, i, q, cur);
                    return;
                }
                max = Math.max(max, cur);
            }
            reArrangeArray(nums, -1, q, Integer.MAX_VALUE);
        }
        
        private static void reArrangeArray(int[] nums, int i, Queue<Integer> q, int t) {
            int j = i + 1;
            boolean isSet = false;
            while(!q.isEmpty()) {
                int cur = q.poll();
                if(t < cur && !isSet) {
                    nums[i] = cur;
                    isSet = true;
                } else {
                    nums[j++] = cur;
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.