Question

1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

中文文档

Description

You are given a string num, representing a large integer, and an integer k.

We call some integer wonderful if it is a permutation of the digits in num and is greater in value than num. There can be many wonderful integers. However, we only care about the smallest-valued ones.

• For example, when num = "5489355142":
  • The 1^st smallest wonderful integer is "5489355214".
  • The 2^nd smallest wonderful integer is "5489355241".
  • The 3^rd smallest wonderful integer is "5489355412".
  • The 4^th smallest wonderful integer is "5489355421".

Return _the minimum number of adjacent digit swaps that needs to be applied to _num_ to reach the _kth_ smallest wonderful integer_.

The tests are generated in such a way that kth smallest wonderful integer exists.

 

Example 1:

Input: num = "5489355142", k = 4
Output: 2
Explanation: The 4th smallest wonderful number is "5489355421". To get this number:
- Swap index 7 with index 8: "5489355142" -> "5489355412"
- Swap index 8 with index 9: "5489355412" -> "5489355421"

Example 2:

Input: num = "11112", k = 4
Output: 4
Explanation: The 4th smallest wonderful number is "21111". To get this number:
- Swap index 3 with index 4: "11112" -> "11121"
- Swap index 2 with index 3: "11121" -> "11211"
- Swap index 1 with index 2: "11211" -> "12111"
- Swap index 0 with index 1: "12111" -> "21111"

Example 3:

Input: num = "00123", k = 1
Output: 1
Explanation: The 1st smallest wonderful number is "00132". To get this number:
- Swap index 3 with index 4: "00123" -> "00132"

 

Constraints:

• 2 <= num.length <= 1000
• 1 <= k <= 1000
• num only consists of digits.

Solutions

Solution 1: Find Next Permutation + Inversion Pairs

We can call the next_permutation function $k$ times to get the $k$th smallest permutation $s$.

Next, we just need to calculate how many swaps are needed for $num$ to become $s$.

Let's first consider a simple situation where all the digits in $num$ are different. In this case, we can directly map the digit characters in $num$ to indices. For example, if $num$ is "54893" and $s$ is "98345". We map each digit in $num$ to an index, that is:

$$ \begin{aligned} num[0] &= 5 &\rightarrow& \quad 0 \ num[1] &= 4 &\rightarrow& \quad 1 \ num[2] &= 8 &\rightarrow& \quad 2 \ num[3] &= 9 &\rightarrow& \quad 3 \ num[4] &= 3 &\rightarrow& \quad 4 \ \end{aligned} $$

Then, mapping each digit in $s$ to an index results in "32410". In this way, the number of swaps needed to change $num$ to $s$ is equal to the number of inversion pairs in the index array after $s$ is mapped.

If there are identical digits in $num$, we can use an array $d$ to record the indices where each digit appears, where $d[i]$ represents the list of indices where the digit $i$ appears. To minimize the number of swaps, when mapping $s$ to an index array, we only need to greedily select the index of the corresponding digit in $d$ in order.

Finally, we can directly use a double loop to calculate the number of inversion pairs, or we can optimize it with a Binary Indexed Tree.

The time complexity is $O(n \times (k + n))$, and the space complexity is $O(n)$. Where $n$ is the length of $num$.

class Solution:
  def getMinSwaps(self, num: str, k: int) -> int:
    def next_permutation(nums: List[str]) -> bool:
      n = len(nums)
      i = n - 2
      while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
      if i < 0:
        return False
      j = n - 1
      while j >= 0 and nums[j] <= nums[i]:
        j -= 1
      nums[i], nums[j] = nums[j], nums[i]
      nums[i + 1 : n] = nums[i + 1 : n][::-1]
      return True

    s = list(num)
    for _ in range(k):
      next_permutation(s)
    d = [[] for _ in range(10)]
    idx = [0] * 10
    n = len(s)
    for i, c in enumerate(num):
      j = ord(c) - ord("0")
      d[j].append(i)
    arr = [0] * n
    for i, c in enumerate(s):
      j = ord(c) - ord("0")
      arr[i] = d[j][idx[j]]
      idx[j] += 1
    return sum(arr[j] > arr[i] for i in range(n) for j in range(i))

class Solution {
  public int getMinSwaps(String num, int k) {
    char[] s = num.toCharArray();
    for (int i = 0; i < k; ++i) {
      nextPermutation(s);
    }
    List<Integer>[] d = new List[10];
    Arrays.setAll(d, i -> new ArrayList<>());
    int n = s.length;
    for (int i = 0; i < n; ++i) {
      d[num.charAt(i) - '0'].add(i);
    }
    int[] idx = new int[10];
    int[] arr = new int[n];
    for (int i = 0; i < n; ++i) {
      arr[i] = d[s[i] - '0'].get(idx[s[i] - '0']++);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (arr[j] > arr[i]) {
          ++ans;
        }
      }
    }
    return ans;
  }

  private boolean nextPermutation(char[] nums) {
    int n = nums.length;
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      --i;
    }
    if (i < 0) {
      return false;
    }
    int j = n - 1;
    while (j >= 0 && nums[i] >= nums[j]) {
      --j;
    }
    swap(nums, i++, j);
    for (j = n - 1; i < j; ++i, --j) {
      swap(nums, i, j);
    }
    return true;
  }

  private void swap(char[] nums, int i, int j) {
    char t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
  }
}

class Solution {
public:
  int getMinSwaps(string num, int k) {
    string s = num;
    for (int i = 0; i < k; ++i) {
      next_permutation(begin(s), end(num));
    }
    vector<int> d[10];
    int n = num.size();
    for (int i = 0; i < n; ++i) {
      d[num[i] - '0'].push_back(i);
    }
    int idx[10]{};
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
      arr[i] = d[s[i] - '0'][idx[s[i] - '0']++];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (arr[j] > arr[i]) {
          ++ans;
        }
      }
    }
    return ans;
  }
};

func getMinSwaps(num string, k int) (ans int) {
  s := []byte(num)
  for ; k > 0; k-- {
    nextPermutation(s)
  }
  d := [10][]int{}
  for i, c := range num {
    j := int(c - '0')
    d[j] = append(d[j], i)
  }
  idx := [10]int{}
  n := len(s)
  arr := make([]int, n)
  for i, c := range s {
    j := int(c - '0')
    arr[i] = d[j][idx[j]]
    idx[j]++
  }
  for i := 0; i < n; i++ {
    for j := 0; j < i; j++ {
      if arr[j] > arr[i] {
        ans++
      }
    }
  }
  return
}

func nextPermutation(nums []byte) bool {
  n := len(nums)
  i := n - 2
  for i >= 0 && nums[i] >= nums[i+1] {
    i--
  }
  if i < 0 {
    return false
  }
  j := n - 1
  for j >= 0 && nums[j] <= nums[i] {
    j--
  }
  nums[i], nums[j] = nums[j], nums[i]
  for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
    nums[i], nums[j] = nums[j], nums[i]
  }
  return true
}

function getMinSwaps(num: string, k: number): number {
  const n = num.length;
  const s = num.split('');
  for (let i = 0; i < k; ++i) {
    nextPermutation(s);
  }
  const d: number[][] = Array.from({ length: 10 }, () => []);
  for (let i = 0; i < n; ++i) {
    d[+num[i]].push(i);
  }
  const idx: number[] = Array(10).fill(0);
  const arr: number[] = [];
  for (let i = 0; i < n; ++i) {
    arr.push(d[+s[i]][idx[+s[i]]++]);
  }
  let ans = 0;
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < i; ++j) {
      if (arr[j] > arr[i]) {
        ans++;
      }
    }
  }
  return ans;
}

function nextPermutation(nums: string[]): boolean {
  const n = nums.length;
  let i = n - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }
  if (i < 0) {
    return false;
  }
  let j = n - 1;
  while (j >= 0 && nums[i] >= nums[j]) {
    j--;
  }
  [nums[i], nums[j]] = [nums[j], nums[i]];
  for (i = i + 1, j = n - 1; i < j; ++i, --j) {
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
  return true;
}