Skip to content

1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int getMinSwaps(string num, int k) {
    string perm = num;

    while (k-- > 0)
      next_permutation(perm.begin(), perm.end());

    return countSteps(num, perm);
  }

 private:
  int countSteps(const string& A, string& B) {
    int count = 0;

    for (int i = 0, j = 0; i < A.length(); ++i) {
      j = i;
      while (A[i] != B[j])
        ++j;
      while (i < j) {
        swap(B[j], B[j - 1]);
        --j;
        ++count;
      }
    }

    return count;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
  public int getMinSwaps(String num, int k) {
    int[] original = new int[num.length()];

    for (int i = 0; i < original.length; ++i)
      original[i] = num.charAt(i) - '0';

    int[] permutated = original.clone();

    for (int i = 0; i < k; ++i)
      nextPermutation(permutated);

    return countSteps(original, permutated);
  }

  public void nextPermutation(int[] nums) {
    final int n = nums.length;

    // From the back to the front, find the first num < nums[i + 1].
    int i;
    for (i = n - 2; i >= 0; --i)
      if (nums[i] < nums[i + 1])
        break;

    // From the back to the front, find the first num > nums[i] and swap it with nums[i].
    if (i >= 0)
      for (int j = n - 1; j > i; --j)
        if (nums[j] > nums[i]) {
          swap(nums, i, j);
          break;
        }

    // Reverse nums[i + 1..n - 1].
    reverse(nums, i + 1, n - 1);
  }

  private void reverse(int[] nums, int l, int r) {
    while (l < r)
      swap(nums, l++, r--);
  }

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

  private int countSteps(int[] A, int[] B) {
    int count = 0;

    for (int i = 0, j = 0; i < A.length; ++i) {
      j = i;
      while (A[i] != B[j])
        ++j;
      while (i < j) {
        swap(B, j, j - 1);
        --j;
        ++count;
      }
    }

    return count;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution:
  def getMinSwaps(self, num: str, k: int) -> int:
    original = [int(c) for c in num]
    permutated = original.copy()

    for _ in range(k):
      self._nextPermutation(permutated)

    return self._countSteps(original, permutated)

  def _nextPermutation(self, nums: list[int]):
    n = len(nums)

    # From the back to the front, find the first num < nums[i + 1].
    i = n - 2
    while i >= 0:
      if nums[i] < nums[i + 1]:
        break
      i -= 1

    # From the back to the front, find the first num > nums[i] and swap it with nums[i].
    if i >= 0:
      for j in range(n - 1, i, -1):
        if nums[j] > nums[i]:
          nums[i], nums[j] = nums[j], nums[i]
          break

    def reverse(nums, l, r):
      while l < r:
        nums[l], nums[r] = nums[r], nums[l]
        l += 1
        r -= 1

    # Reverse nums[i + 1..n - 1].
    reverse(nums, i + 1, len(nums) - 1)

  def _countSteps(self, A: list[int], B: list[int]) -> int:
    count = 0

    j = 0
    for i in range(len(A)):
      j = i
      while A[i] != B[j]:
        j += 1
      while i < j:
        B[j], B[j - 1] = B[j - 1], B[j]
        j -= 1
        count += 1

    return count