检查数字重复数字的最快方法是什么？

一尘不染

检查数字重复数字的最快方法是什么？

algorithm

假设我要检查数字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 ++编写，仅用于描述目的。我必须用9位数字在TI-89中解决此问题。由于内存和速度的限制，我正在寻找最快的方法。

TI-89仅具有几个条件关键字：

如果
如果…那么
什么时候（
对于… EndFor
虽然… EndWhile
循环… EndLoop
自定义… EndCustom

谢谢
陈

阅读 292

2020-07-28

共1个答案

一尘不染

速度可能更快，但可能不会（但是您还是应该进行测量，以防万一-我的优化口号是"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]。

根据您需要处理九位数字时的编辑，可能无法在计算器上使用十亿元素数组（上述第二个解决方案）：-)

我会选择第一个解决方案。

2020-07-28