Yet another clear Java O(N) solution


  • 0
    J
    public class Solution {
        private void swap(int[] nums, int l, int r) {
            int t = nums[l];
            nums[l] = nums[r];
            nums[r] = t;
        }
        private int binarySearch(int[] nums, int l, int r, int key) {
            while (l <= r) {
                int m = (l + r) >> 1;
                if (nums[m] < key) r = m - 1;
                else l = m + 1;
            }
            return r;
        }
        public void nextPermutation(int[] nums) {
            if (nums.length < 2) return;
            int i = nums.length - 2;
            for (; i >= 0; i--) if (nums[i + 1] > nums[i]) break;
            if (i > -1) {
                int idx = binarySearch(nums, i + 1, nums.length - 1, nums[i] + 1);
                swap(nums, i, idx);
            }
            int l = i + 1;
            int r = nums.length - 1;
            while (l < r) swap(nums, l++, r--);
        }
    }
    

Log in to reply
 

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