Java O(n), straightforward


  • 0
    J
        public void nextPermutation(int[] nums) {
            if (nums.length <= 1) return;
            int revIdx = nums.length - 1;
            for (; revIdx >= 0; revIdx --) {
                if (revIdx == 0 || nums[revIdx] > nums[revIdx - 1]) break;;
            }
            if (revIdx == 0) reverse(nums, 0, nums.length - 1);
            else {
                reverse(nums, revIdx, nums.length - 1);
                for (int i = revIdx; i < nums.length; i++) {
                    if (nums[i] > nums[revIdx - 1]) {
                        swap(nums, revIdx - 1, i);
                        break;
                    }
                }
            }
        }
        
        void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        
        void reverse(int[] n, int start, int end) {
            while (start < end) {
                swap(n, start, end);
                start++;
                end--;
            }
        }
    

Log in to reply
 

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