檢查號碼重複數字的最快方法是什麼？

假設我想檢查一個數字n = 123是否有重複的數字。我試過：檢查號碼重複數字的最快方法是什麼？

#include <iostream> 

using namespace std; 

int main() { 
    int n = 123; 
    int d1 = n % 10; 
    int d2 = (n/10) % 10; 
    int d3 = (n/100) % 10; 
    if(d1 != d2 && d1 != d3 && d2 != d3) { 
     cout << n << " does not have duplicate digits.\n"; 
    } 
}

有沒有更快的解決方案來解決這個問題？

更新
對不起，不清楚。上面的代碼是用C++編寫的，僅用於描述目的。我必須在TI-89中解決這個問題，其中有9位數字。由於內存和速度的限制，我正在尋找一種最快的方式。

TI-89只有幾個條件關鍵字：

如果
如果...那麼
時（
對於... ENDFOR
雖然... ENDWHILE
Loop ... EndLoop
Custom ... EndCustom

感謝，
陳

來源

2011-01-26 Chan

由於您的解決方案僅限於三位數字，只需製作具有重複數字的數字的哈希表，並檢查數字是否包含在其中。 – aaronasterling 2011-01-26 04:54:48

您還需要處理少於三位的數字（如果這是有效的輸入）。現在`n = 1`將被拒絕爲重複數字（前導零）。 – Thilo 2011-01-26 05:07:43

您正在使用TI-89上的哪種語言？ – 2011-01-26 05:11:15

更快，可能沒有（但你無論如何都應該衡量，以防萬一 - 我的優化口頭禪是"measure, don't guess"）。但意圖更清晰，我認爲，是的，並且能夠處理任意大小的整數。

int hasDupes (unsigned int n) { 
    // Flag to indicate digit has been used. 

    int i, used[10]; 

    // Must have dupes if more than ten digits. 

    if (n > 9999999999) 
     return 1; 

    // Initialise dupe flags to false. 

    for (i = 0; i < 10; i++) 
     used[i] = 0; 

    // Process all digits in number. 

    while (n != 0) { 
     // Already used? Return true. 

     if (used[n%10]) // you can cache n%10 if compiler not too smart. 
      return 1; 

     // Otherwise, mark used, go to next digit. 

     used[n%10] = 1; // and you would use cached value here. 
     n /= 10; 
    } 

    // No dupes, return false. 

    return 0; 
}

如果你有機會在有限的範圍內，你可以使用時間犧牲空間的由來已久的做法。

說你0和999之間談論的數字：

const int *hasDupes = { 
// 0 1 2 3 4 5 6 7 8 9 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // x 
    0, 1, 0, 0, 0, 0, 0, 0, 0, 0, // 1x 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, // 2x 
    : 
    0, 0, 0, 0, 0, 0, 0, 1, 0, 1, // 97x 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 1, // 98x 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 99x 
};

，只是做的hasDupes[n]查表。

基礎上，當你需要處理的九位，一個數十億元素的數組（上面第二個解決方案）的編輯很可能不會有可能在計算器:-)

我會選擇第一個解決方案。

來源

2011-01-26 04:54:06 paxdiablo

template<class T, int radix = 10> 
bool has_duplicate_digits(T n) { 
    int digits_mask = 0; 
    while (digits_mask |= (1 << (n % radix)), n /= radix) 
     if (digits_mask & (1 << (n % radix))) 
      return true; 
    return false; 
}

類似的東西應該只要n爲負，並且int具有至少radix位工作。

digits_mask是一個bitset（位0代表一個0數字的發生，位1表示1位等的發生）。

位圖填充了n的最低有效位，其餘位數向下移位。如果有更多數字，並且新的最低有效數字被標記爲先前已發生，則返回true，否則重複。

當沒有更多數字時，返回false。

1 << x返回1,2,4,8等：用於測試/設置比特位的掩碼。

a |= z是a = a | z的簡寫，它通過a的聯合從z來設置比特。

a & z是a和z中的位的相交，如果沒有設置，則爲零（假），如果設置了任何值，則爲非零（真）。

來源

2011-01-26 05:17:33 ephemient

我做了一個速成班在TI-89的基本回答:)

讓我們來看看這是否正常工作（我沒有一個模擬器，所以無法查詢）。

Test() 
Prgm 
{0,0,0,0,0,0,0,0,0,0}->A 
Title "Request" 
Request "Enter a number",B 
EndDlog 
Expr(B)->B 
While B > 1 
MOD(10,B)->C 
if A[C+1] = 1 goto K 
1->A[C+1] 
B-C->B 
EndWhile 
Title "Done" 
Text "Numbers non repeating" 
Enddlog 
goto J 

Lbl K 
Title "Done" 
Text "Numbers repeating" 
Enddlog 

Lbl J 
EndPrgm

來源

2011-01-26 06:07:56

檢查號碼重複數字的最快方法是什麼？

回答

相關問題