邻位交换的最小次数

2021-05-02

5749. 邻位交换的最小次数

难度中等0

给你一个表示大整数的字符串 num ，和一个整数 k 。

如果某个整数是 num 中各位数字的一个排列且它的 值大于 num ，则称这个整数为妙数。可能存在很多妙数，但是只需要关注 值最小 的那些。

例如，
1
num = "5489355142"

：

第 1 个最小妙数是 "5489355214"
第 2 个最小妙数是 "5489355241"
第 3 个最小妙数是 "5489355412"
第 4 个最小妙数是 "5489355421"

返回要得到第 k 个 最小妙数 需要对 num 执行的 相邻位数字交换的最小次数 。

测试用例是按存在第 k 个最小妙数而生成的。

示例 1：

输入：num = "5489355142", k = 4
输出：2
解释：第 4 个最小妙数是 "5489355421" ，要想得到这个数字：
- 交换下标 7 和下标 8 对应的位："5489355142" -> "5489355412"
- 交换下标 8 和下标 9 对应的位："5489355412" -> "5489355421"

示例 2：

输入：num = "11112", k = 4
输出：4
解释：第 4 个最小妙数是 "21111" ，要想得到这个数字：
- 交换下标 3 和下标 4 对应的位："11112" -> "11121"
- 交换下标 2 和下标 3 对应的位："11121" -> "11211"
- 交换下标 1 和下标 2 对应的位："11211" -> "12111"
- 交换下标 0 和下标 1 对应的位："12111" -> "21111"

示例 3：

输入：num = "00123", k = 1
输出：1
解释：第 1 个最小妙数是 "00132" ，要想得到这个数字：
- 交换下标 3 和下标 4 对应的位："00123" -> "00132"

提示：

2 <= num.length <= 1000
1 <= k <= 1000
num 仅由数字组成

生成下一个全排列

class Solution {
    public int getMinSwaps(String s, int k) {
        char[] target = s.toCharArray();
		// 生成要得到的那个数字
        for (int i = 0; i < k; i++) {
            nextPermutation(target);
            // System.out.println(String.valueOf(target));
        }
        
        // 计算从原始数字到当前数字总共经过了几步变化
        char[] num = s.toCharArray();
        int n = num.length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            // 从左往右遍历,如果当前的数字与目标数字不同,那么找到相同的那个数字,然后相同的那个数字一直交换到与当前元素相同的位置,每交换一次结果+1,继续下次循环
            if (num[i] != target[i]) {
                int j = i + 1;
                while (j < n && num[j] != target[i])
                    j++;
                for (; j > i && j < n; --j) {
                    swap(num, j, j - 1);
                    ans++;
                }
            }
        }
        return ans;
    }


    public boolean nextPermutation(char[] num) {
        if (num.length <= 1) return false;
        for (int i = num.length - 2; i >= 0; i--) {
            if (num[i] < num[i + 1]) {
                int j;
                for (j = num.length - 1; j >= i; j--) {
                    if (num[i] < num[j]) break;
                }
                // swap the two numbers.
                // num[i] = num[i] ^ num[j];
                // num[j] = num[i] ^ num[j];
                // num[i] = num[i] ^ num[j];
                swap(num, i, j);
                //sort the rest of arrays after the swap point.
                Arrays.sort(num, i + 1, num.length);
                return true;
            }
        }
        //reverse the arrays.
        for (int i = 0; i < num.length / 2; i++) {
            // int tmp = num[i];
            // num[i] = num[num.length - i - 1];
            // num[num.length - i - 1] = tmp;
            swap(num, i, num.length - i - 1);
        }
        return false;
    }

    public void swap(char[] arr, int index1, int index2) {
        char temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

生成下一个全排列


public boolean nextPermutation(int[] num) {
    if (num.length <= 1) return false;
    // 从后往前选择数字，直到找到一个数字的连续两位是升序的
    // 这个时候从最后开始遍历,找到一个元素大于前面选择的数字
    // 交换这两个元素
    // 并对第一个元素之后的所有元素排序
    for (int i = num.length - 2; i >= 0; i--) {
        if (num[i] < num[i + 1]) {
            int j;
            for (j = num.length - 1; j >= i; j--) {
                if (num[i] < num[j]) break;
            }
            // swap the two numbers.
            num[i] = num[i] ^ num[j];
            num[j] = num[i] ^ num[j];
            num[i] = num[i] ^ num[j];
            //sort the rest of arrays after the swap point.
            Arrays.sort(num, i + 1, num.length);
            return true;
        }
    }
    // 如果遍历到最后都不是逆序的了,将当前的数组逆序,并返回false
    
    //reverse the arrays.
    for (int i = 0; i < num.length / 2; i++) {
        int tmp = num[i];
        num[i] = num[num.length - i - 1];
        num[num.length - i - 1] = tmp;
    }
    return false;
}

原始版本链接

public void nextPermutation(int[] num) {
    if (num.length <= 1)
        return;
    for (int i = num.length - 2; i >= 0; i--) {
        if (num[i] < num[i + 1]) {
            int j;
            for (j = num.length - 1; j >= i; j--)
                if (num[i] < num[j])
                    break;
            // swap the two numbers.  
            num[i] = num[i] ^ num[j];
            num[j] = num[i] ^ num[j];
            num[i] = num[i] ^ num[j];
            //sort the rest of arrays after the swap point.  
            Arrays.sort(num, i + 1, num.length);
            return;
        }
    }
    //reverse the arrays.  
    for (int i = 0; i < num.length / 2; i++) {
        int tmp = num[i];
        num[i] = num[num.length - i - 1];
        num[num.length - i - 1] = tmp;
    }
    return;
}

参考文献

java有自带类似于c++里面的next_permutation函数吗?_百度知道 (baidu.com)