Java, PriorityQueue with detail explanation, O(NlogN)


  • 0
    1. char[] chars = (""+num).toCharArray();

    2. PriorityQueue pq store the index of the digit in num, large digit first; for same digit, lower index first

    3. Iterate the chars, find the first mismatch, chars[i] != chars[pq.poll()]; at this time, max = chars[pq.poll()] is the largest digit we can put here.

    4. Then we want to swap chars[i] with the last appearance of the digit max (e.g. 98368, swap 3 with the last 8);

    Example:
    input: 9-8-3-6-8
    index: 0-1-2-3-4

    pq : 0-1-4-3-2

    for (int i = 0; i < chars.length; i++)
    chars[0] == chars[pq.poll() = 0]; i++
    chars[1] == chars[pq.poll() = 1]; i++
    chars[2] != chars[pq.poll() = 4]; i++

    so we want to swap chars[2] with chars[4]

    class Solution {
        public int maximumSwap(int num) {
            char[] chars = (""+num).toCharArray();
            PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
                @Override
                public int compare(Integer a, Integer b) {
                    if (chars[a] == chars[b]){
                        return a-b; //idx increasing
                    }
                    return chars[b] - chars[a]; // digit desending
                }
            });
            for (int i = 0; i < chars.length; i++)
                pq.offer(i);
                    
            for (int i = 0; i < chars.length; i++){
                int idx = pq.poll();
                char max = chars[idx];
                if (chars[i] != max) {
                    char ch = chars[i];      
                    while (!pq.isEmpty() && chars[pq.peek()] == max) 
                        idx = pq.poll();
                    chars[i] = max;
                    chars[idx] = ch;
                    break;
                }
            }
    
            return Integer.parseInt(new String(chars));
        }
    }
    

Log in to reply
 

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