計算具有唯一數字的數字

1. 概述

在本文中，我們將探討計數具有唯一數字的數字的問題，使得數字的總位數不超過給定的整數。

我們將透過範例和時間和空間複雜性的分析來研究從蠻力到最佳化方法的有效解決方案。

2.問題陳述

給定一個整數n ，我們需要計算所有具有唯一數字的正數x ，使得：

• 0 <= x < 10 n ie, xi是小於10 n正整數
• x中的每個數字都是唯一的，沒有重複

以下是一些範例：

• 如果n = 0 ，則唯一滿足我們條件的數字是0
• 如果n = 1 ，則所有一位數都計數： 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
• 如果n = 2 ，則所有一位數都算： 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13等（注意，不包括 11）
• 如果n = 3 ，則唯一數字小於1000的數字將包括0, 1, 2, 3, 12, 13, 23, 345, 745等。
• 如果n = 4 ，則唯一數字小於1000的數字將包括0, 1, 2, 3, 12, 13, 23, 345, 745, 1234, 1567等。

3.解決方案

3.1.強力方法

一種直接的方法是強力方法，它涉及產生小於10 n所有數字並檢查每個數字是否都有唯一的數字。然而，隨著n增加，計算成本會變得越來越高。

在蠻力法中，我們循環遍歷所有小於10 n數字。對於每個數字，驗證其數字是否唯一，並計算有多少個數字符合此條件：

int bruteForce(int n) {

 int count = 0;

 int limit = (int) Math.pow(10, n);



 for (int num = 0; num < limit; num++) {

 if (hasUniqueDigits(num)) {

 count++;

 }

 }

 return count;

 }

hasUniqueDigits函數透過將給定的數字轉換為字串並將每個數字與其他數字進行比較來檢查該數字是否沒有重複的數字。如果發現任何重複的數字，則傳回false ；否則，回傳true ：

boolean hasUniqueDigits(int num) {

 String str = Integer.toString(num);

 for (int i = 0; i < str.length(); i++) {

 for (int j = i + 1; j < str.length(); j++) {

 if (str.charAt(i) == str.charAt(j)) {

 return false;

 }

 }

 }

 return true;

 }

讓我們透過執行以下測試來驗證演算法：

@Test

 void givenNumber_whenUsingBruteForce_thenCountNumbersWithUniqueDigits() {

 assertEquals(91, UniqueDigitCounter.bruteForce(2));

 }

時間複雜度為O(10 n ) ，其中 n 為最大數字的位數，因為我們檢查每個數字的數字是否唯一。由於每個數字的字串表示，因此空間複雜度為O(n) 。

3.2.組合方法

為了優化流程，我們可以採用組合方法。我們不使用蠻力，而是透過單獨考慮每個數字的位置並利用排列來計算有效數字的數量。

這種方法比蠻力破解更有效。它只需要對每個數字進行恆定的工作，這使得更大的n.

讓我們看看以下觀察：

• 當n = 0,回傳 1，因為唯一有效的數字是0
• 當n = 1,數字可以是0到9 ，因此有10可能的數字
• 當n > 1:
  • 第一位數字有9可能的選擇（ 1到9 ，因為0不能作為第一位數字）
  • 第二位數字有9可能的選擇（ 0到9 ，不包括第一位數字）
  • 第三位數字有8選擇，依此類推

對於k位數字，可以使用排列來計算有效數字的數量：

int combinatorial(int n) {

 if (n == 0) return 1;



 int result = 10;

 int current = 9;

 int available = 9;



 for (int i = 2; i <= n; i++) {

 current *= available;

 result += current;

 available--;

 }

 return result;

 }

讓我們測試一下上述方法是否正確運作：

@Test

 void givenNumber_whenUsingCombinatorial_thenCountNumbersWithUniqueDigits() {

 assertEquals(91, UniqueDigitCounter.combinatorial(2));

 }

時間複雜度為O(n) ，因為我們處理每個數字一次，而空間複雜度為O(1)因為我們只使用幾個變數。

4. 結論

在本文中，我們探討了兩種計數小於n的唯一數字的方法。強力方法會檢查所有數字，但對於較大的n來說效率低下，而組合方法則使用排列來獲得高效的O(n)解決方案。

與往常一樣，完整的原始程式碼可在 GitHub 上取得。