2024年1月22日每日一题--670. 最大交换

670. 最大交换

题目分析

方案一

既然只能交换一次，所以最简单粗暴的想法就是固定第一个，然后找后面的位数相关数据是否比第一位大

 class Solution {
    public int maximumSwap(int num) {
        
        StringBuilder numStr = new StringBuilder(String.valueOf(num));
        char start = numStr.charAt(0);
        char maxChar = '0';
        int maxIndex = -1;

        for (int i = 1; i < numStr.length(); i++) {
            if (numStr.charAt(i) > start && numStr.charAt(i) > maxChar) {
                maxIndex = i;
                maxChar = numStr.charAt(i);
            }
        }

        if (maxIndex != -1) {
            numStr.replace(0, 1, String.valueOf(maxChar));
            numStr.replace(maxIndex, maxIndex + 1, String.valueOf(start));
        }

        return Integer.parseInt(numStr.toString());

    }
}

结果

想法太简单粗暴，所以没有成功ac

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

方案二

尝试先使用优先队列存储数据，然后对优先队列中的数据进行操作。

class Solution {
    public int maximumSwap(int num) {

        StringBuilder numStr = new StringBuilder(String.valueOf(num)); // 将数据转储为StringBuilder，方便对数值进行换位

        PriorityQueue<Integer[]> queue = new PriorityQueue<>((o1, o2) -> { // 初始化优先队列的相关属性
            int i = o2[0].compareTo(o1[0]); // 第n位的数据从高向底排列
            if (i != 0) return i;
            return o1[1].compareTo(o2[1]); // 第n位的数据相等的时候，按照索引从低向高排列
        });


        for (int i = 0; i < numStr.length(); i++) {
            queue.add(new Integer[]{(int) numStr.charAt(i) - 48, i}); // 安位将数据存储到优先队列中
        }

        int startIndex = 0;
        int maxChar = -1;
        int maxIndex = -1;

        while (!queue.isEmpty()) { // 开始对其进行弹出操作
            Integer[] peek = queue.poll();
            if (peek[1] == startIndex) { // 此时的特殊情况为： 98716 ，其真实的结果是98761，将1和6进行交换
                startIndex++;
            } else {
                maxIndex = peek[1];
                maxChar = peek[0];
                while (!queue.isEmpty()) { // 此时的特殊情况为： 199982 ，其真实的结果是999182，将1和最后一个9进行交换，没有此项，结果将会变为919982
                    Integer[] poll = queue.poll();
                    if (maxChar != poll[0]) break;
                    maxIndex = poll[1];
                }
                break;
            }
        }

        if (maxIndex != -1) {
            int startChar = (int) numStr.charAt(startIndex) - 48;
            numStr.replace(startIndex, startIndex + 1, String.valueOf(maxChar));
            numStr.replace(maxIndex, maxIndex + 1, String.valueOf(startChar));
        }

        return Integer.parseInt(numStr.toString());
    }
}

结果

可以得到最终的结果

分析

时间复杂度：
O( n * log(n) ) 向优先队列添加数据时候，导致的这个时间复杂度。因为每次添加一个数据 的时间 复杂度为 log(n)

空间复杂度：
O( n )

官方题解

https://leetcode.cn/problems/maximum-swap/solutions/1818457/zui-da-jiao-huan-by-leetcode-solution-lnd5/

class Solution {
    public int maximumSwap(int num) {
        char[] charArray = String.valueOf(num).toCharArray();
        int n = charArray.length;
        int maxIdx = n - 1;
        int idx1 = -1, idx2 = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (charArray[i] > charArray[maxIdx]) {
                maxIdx = i;
            } else if (charArray[i] < charArray[maxIdx]) {
                idx1 = i;
                idx2 = maxIdx;
            }
        }
        if (idx1 >= 0) {
            swap(charArray, idx1, idx2);
            return Integer.parseInt(new String(charArray));
        } else {
            return num;
        }
    }

    public void swap(char[] charArray, int i, int j) {
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/maximum-swap/solutions/1818457/zui-da-jiao-huan-by-leetcode-solution-lnd5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

简而言之：时间复杂度和空间复杂度都为n，其中n为num的位数。