Accepted java solution using binary search


  • 0
    M
    public void nextPermutation(int[] num) {
        if (num.length < 2) {
            return;
        }
        int tail = num.length - 1;
        //traverse from the last element, find the first element that is smaller than num[tail]
        while (tail > 0 && num[tail - 1] >= num[tail]) {
            tail--;
        }
        //this means num is in an descending order, just reverse it.
        if (tail == 0) {
            reverse(num, 0, num.length - 1);
            return;
        }
        else {
            //the index of the first element that is smaller than its next (traverse from the end of num)
            int k = tail - 1;
            //find the index of the least element that is larger than num[k], search from num[k-1] to the end
            int nextLarger = firstLarger(num, tail, num.length-1,num[k]);
            //swap these two elements
            swap(num, k, nextLarger);
            //reverse the remaining sub-array
            reverse(num, tail, num.length - 1);
            return;
        }
    }
    //reverse the sub-array, num[i] to num[j]
    public void reverse(int[] num, int i, int j) {
        for (int k = i; k <= (j + i) / 2; k++) {
            swap(num, k, j + i - k);
        }
    }
    //swap num[i] and num[j]
    public void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    
    //find the index of the least element from num[start] to num[end], which is larger than k (binary seaerch)
    public int firstLarger(int[] num, int start, int end, int k) {
        if (end-start+1 == 1) {
            return start;
        }
        int i = start, j = end;
        while (i < j) {
            int mid = (i + j) / 2;
            if (num[mid] == k) {
                while (num[mid] == k) {
                    mid--;
                }
                return mid;
            } else if (num[mid] > k) {
                if (num[mid + 1] <= k) {
                    return mid;
                } else {
                    i = mid + 1;
                }
            } else {
                j = mid - 1;
            }
        }
        return i;
    
    }

Log in to reply
 

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