題目：Next smaller number with the same digits

簡述：設計一個方法 nextSmaller()，給定一個數值，尋找相同數字組合的上一個正整數，如

1
2
3
nextSmaller(21) == 12
nextSmaller(531) == 513
nextSmaller(2071) == 2017

且找到的數字若為 0 開頭，或沒有符合的正整數則傳回 -1，如

1
2
3
4
nextSmaller(9) == -1
nextSmaller(111) == -1
nextSmaller(135) == -1
nextSmaller(1027) == -1 // 0721 is out since we don't write numbers with leading zeros

規則：

  1. 測試案例可能包含非常大的數字。
  2. 數字只會給予正整數。

想破頭還想不出方法，剛好它有另一題類似的題目，從找小一點的變找大一點的，所以與其想到放棄，不如了解其他人是如何解決的，之後再自己解決變相題目。

結果又只是數學問題，本來以為需要找出所有組合，然後再找數字，但又沒辦法在特定時間內完成，沒有想到能用這種方式找出答案。

我認為最清楚的解法：

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
public static long NextSmaller(long n)
{
  int[] a = new int[n.ToString().Length];
  int j = 0;
  // Loading digits into array so easier to work with
  while (n > 0)
  {
    a[j++] = (int)(n % 10);
    n /= 10;
  }

  // Strategy = go from right to left and find the first digit with a number greater to the left
  // eg 285123 - find the '1' because there's a greater number beside
  // Find the biggest number to the right, and switch the two
  // eg 285123 - switch the 5 and the 3 = 283125
  // Then, sort everything to the right of the index in descending order
  // eg 283125 -> 283521

  // find int to move
  int index = 0;
  int highest = 0;
  for (index = 1; index < a.Length; index++)
  {
    if (a[index] > a[index - 1]) break;
  }
  // find biggest digit to the right of it
  if (index >= a.Length) return -1;
  highest = index - 1;
  for (int k = 0; k < index; k++)
  {
    if (a[k] > a[highest] && a[index] > a[k]) highest = k;
  }

  // switch index with highest
  int temp = a[index];
  a[index] = a[highest];
  a[highest] = temp;

  // take array of everything to the right of the index
  int[] b = new int[index];
  for (int i = 0; i < index; i++)
  {
    b[i] = a[i];
  }
  // sort it and copy back
  Array.Sort(b);
  for (int i = 0; i < index; i++)
  {
    a[i] = b[i];
  }

  long output = 0;
  long pos = 1;
  // convert array back into long
  for (int i = 0; i < a.Length; i++)
  {
    output += pos * a[i];
    pos *= 10;
  }
  // if we needed to move a zero to the very left, then the long will be shorter, return -1
  if (output.ToString().Length < a.Length) return -1;
  return output;
}

這一段程式碼很清楚的註解了內容，而內容中的 Array.Sort() 需要 using System，以下是我的程式碼解讀。

  1. 從個位數開始找，找到第一個非遞減的數，當找不到非遞減的數時，傳回 -1。
    1
    2
    3
    5481259 => 54[8]1259 的 8
    5154951156899 => 51549[5]1156899 的 5
    115788 => -1
  2. 然後計算右半邊小於它的最大數字。
    1
    2
    54[8]1259 => 54[8]12(5)9 的 5
    51549[5]1156899 => 51549[5]1(1)56899 的 1
  3. 調換兩數位置。
    1
    2
    54[8]12(5)9 => 54(5)12[8]9
    51549[5]1(1)56899 => 51549(1)1[5]56899
  4. 將新的右半邊變成最大數，也就是我們要的答案。
    1
    2
    54(5)12[8]9 => 54(5)9821
    51549(1)1[5]56899 => 51549(1)9986551

我認為最簡潔的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static long NextSmaller(long n)
{
  if (n > 0 & (n + "").Length == 1) return -1;
  string s = n + "";
  for (int i = s.Length - 2; i >= 0; i--)
  {
    if (s.Substring(i) != string.Concat(s.Substring(i).OrderBy(x => x)))
    {
      var t = string.Concat(s.Substring(i).OrderByDescending(x => x));
      var c = t.First(x => x < s[i]);
      return i == 0 & c == '0' ? -1 : long.Parse(s.Substring(0, i) + c + string.Concat(t.Where((x, y) => y != t.IndexOf(c))));
    }
  }
  return -1;
}

這解法則改用了 Linq，乾淨俐落的表達出與上面解法一樣的內容，程式碼解讀。

  1. 從末兩位數開始檢查，如果是遞增數字則檢查末三位數，以此類推直到檢查完。
    1
    1251233 => 12512[35] => 1251[235] => 125[1235]
  2. 若檢查到有非遞增數字，則將該數組轉換成遞減數組。
    1
    12[51235] => 12[55321]
  3. 尋找第一個小於第一位的數字。
    1
    12[55321] => 12[55(3)21] 的 3
  4. 將上步驟的數字挑出與重組數組。
    1
    12[55(3)21] => 12(3)[5521]

順便紀錄 & 與 && 的差異，當 & 作為二元運算子使用時等同於 &&，差別在 & 即使第一個變數為否也一樣會檢查第二個變數，以下是官方範例。

1
2
3
4
5
6
7
8
9
10
11
bool SecondOperand() 
{
  Console.WriteLine("Second operand is evaluated.");
  return true;
}

bool test = false & SecondOperand();
Console.WriteLine(test);
// Output:
// Second operand is evaluated.
// False

參考資料

& 運算子 - C# 參考