Java(5ms) - Find - Swap - Sort Solution


  • 3

    From right to left, the idea is to find the number greater than num[i], swap it, and sort the rest of the elements to the right.

    public int nextGreaterElement(int n) {
        char[] num = (n + "").toCharArray();
        for(int i = num.length-2; i >= 0; i--) {
            // find min number greater than num(i)
            int minIdx = i;
            for(int j = i+1; j < num.length; j++) {
                minIdx = num[j] > num[i] ? j : minIdx;
            }
            if(minIdx != i) {
                char temp = num[i]; //swap minIdx and i;
                num[i] = num[minIdx];
                num[minIdx] = temp;
                
                Arrays.sort(num, i+1, num.length);
    
                long val = Long.parseLong(new String(num));
                return (val <= Integer.MAX_VALUE) ? (int) val : -1;
            }
        }
        return -1;
    }

  • 0
    J

    @jaqenhgar how is it find minIdx ?


  • 0
    Z

    My idea is the same in general. I have decided to share my code below.

    public class Solution {
        
        private List<Integer> parseDigits(int n){
            List<Integer> res = new ArrayList<>();
            while(n != 0){
                res.add(n%10);
                n/=10;
            }
            return res;
        }
        
        private int makeNumber(int [] digs){
            int res= 0;
            int p = 1;
            for(int dig:digs){
                res+=dig*p;
                p*=10;
            }
            return res;
        }
        
        private void swap(int nums[], int i, int j){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        
        private void reverse(int nums[], int i, int j){
            int l = i;
            int r = j-1;
            while(l<r){
                swap(nums, l, r);
                l++;
                r--;
            }
            
        }
        
        public int nextGreaterElement(int n) {
            if(n == 0) return n;
            List<Integer> digs =  parseDigits(n);
            int [] nums = new int[digs.size()];
            for(int i = 0;i<digs.size();i++) nums[i] = digs.get(i);
            for(int i = 0;i<nums.length;i++){
                int cur = nums[i];
                Arrays.sort(nums,0,i);
                for(int j = 0;j<i;j++){
                    if(nums[j] > cur){
                        swap(nums, i, j);
                        break;
                    }
                }
                Arrays.sort(nums, 0, i);
                reverse(nums, 0, i);
                int m = makeNumber(nums);
                if(m >n) return m;
            }
            return -1;
        }
    }

  • 0
    H
    This post is deleted!

  • 0
    H

    It's already sorted, so it takes 2ms more.

    Arrays,sort(num, i+1 num.length);

  • 0
    C

    @jaqenhgar My idea is also like this,but your program is so Short and simple.


  • 0

    @hantong It is, but it's in the reverse order. I'm using sort to reverse it.


  • 0

    i've got almost the same idea but w/o sorting, which takes 3ms:

    public class Solution {
        public int nextGreaterElement(int n) {
            int m = n, size = 0, peak = 1, list[] = new int[10];
            while (m != 0) {
                list[size++] = m % 10;
                m /= 10;
            }
    
            while (peak < size) {
                if (list[peak] < list[peak - 1]) {
                    int cursor = 0, result = 0;
                    while (list[cursor] <= list[peak]) cursor++;
                    int tmp = list[cursor];
                    list[cursor] = list[peak];
                    list[peak] = tmp;
                    for (int i = size - 1; i >= peak; i--) result = result * 10 + list[i];
                    for (int j = 0; j < peak; j++) result = result * 10 + list[j];
                    return result > n ? result : -1;
                }
                peak++;
            }
            return -1;
        }
    }
    

  • 0
    D

    I'm not even able to read the question. WTF, could someone explain this problem in a simple way to me?


  • 1

    @danielz92 Consider the number 3142. You need to get the first number which is greater than 3142, but the condition is that you've the reuse the numbers in 3142, that is - [3,1,4,2]

    If you look at it, some of the possible numbers are, 3412, 4213, 3241, 3214, etc.. (all greater than 3142). But the least among them is 3214, which is what this question asks you to find.


  • 0
    A

    @jedxin It doesn't.

    Made a slight change on finding the minIdx (AKA, the index of the smallest number that is larger than the current digit):

               //set minIdx to be current digit
                int minIdx = i;
                //find the first digit that is greater than current digit
                for (int k = i; k < num.length; ++k) {
                    if (num[k] > num[minIdx]){
                        minIdx = k;
                        break;
                    }
                }
               //continue to search if this index is "minimal", if not, update
                for(int j = i+1; j < num.length; j++) {
                    if (num[j] > num[i] && minIdx != i && num[j] < num[minIdx])
                        minIdx = j;
                }
    

Log in to reply
 

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