Minimum Adjacent Swaps to Reach the Kth Smallest Number LeetCode solution in Java

1
class Solution {
2
  public int getMinSwaps(String num, int k) {
3
    int[] nums = new int[num.length()];
4
    int[] org = new int[num.length()];
5

6
    for (int i = 0; i < num.length(); i++) {
7
      int e = Character.getNumericValue(num.charAt(i));
8
      nums[i] = e;
9
      org[i] = e;
10
    }
11

12
    while (k != 0) {
13
      nextPermutation(nums);
14
      k--;
15
    }
16

17
    int ans = 0;
18

19
    for (int i = 0; i < nums.length; i++) {
20

21
      if (nums[i] != org[i]) {
22
        int j = 0;
23
        for (j = i + 1; j < nums.length; j++) if (org[j] == nums[i]) break;
24

25
        while (j > 0 && j != i) {
26
          swap(org, j, j - 1);
27
          ans++;
28
          j--;
29
        }
30
      }
31
    }
32

33
    return ans;
34
  }
35

36
  public void nextPermutation(int[] nums) {
37

38
    if (nums.length <= 1) return;
39

40
    int j = nums.length - 2;
41
    while (j >= 0 && nums[j] >= nums[j + 1]) j--;
42

43
    if (j >= 0) {
44
      int k = nums.length - 1;
45
      while (nums[j] >= nums[k]) k--;
46

47
      swap(nums, j, k);
48
    }
49

50
    reverse(nums, j + 1, nums.length - 1);
51
  }
52

53
  public void swap(int[] nums, int j, int k) {
54
    int temp = nums[j];
55
    nums[j] = nums[k];
56
    nums[k] = temp;
57
  }
58

59
  public void reverse(int[] nums, int i, int j) {
60
    while (i <= j) {
61
      swap(nums, i, j);
62
      i++;
63
      j--;
64
    }
65
  }
66
}