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

Question

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

6

假设我想检查一个数字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仅具有几个条件关键字：

If
If ... Then
when(
For ... EndFor
While ... EndWhile
Loop ... EndLoop
Custom ... EndCustom

谢谢，
Chan

- roxrook

由于您的解决方案仅限于三位数，因此只需创建一个具有重复数字的数字的哈希表，并检查该数字是否包含在其中即可。 - aaronasterling

您还需要处理少于三位数的数字（如果这是有效输入）。现在，n = 1将被拒绝，因为它具有重复的数字（前导零）。 - Thilo

你在 TI-89 上使用哪种语言工作？ - Dr. belisarius

@belisarius：哇，我不知道我可以使用C语言。但是从内置关键字列表中看，它似乎不像C函数。 - roxrook

1

@Chan 请查看TI-89语言推荐的以下网站：http://www.ocf.berkeley.edu/~pad/faq/prog.html - Dr. belisarius

显示剩余4条评论

3个回答

3

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是一个位集（第0位表示0出现的次数，第1位表示1出现的次数等等）。

位图用n的最低有效数字填充，其余数字向下移位。如果有更多数字，并且新的最低有效数字被标记为之前出现过，则返回true，否则重复此步骤。

当没有更多数字时，返回false。 1 << x返回1、2、4、8等：在位集中测试/设置位的掩码。 a |= z是a = a | z的简写，它通过从z到a的联合来设置位。 a & z是a和z中位的交集，如果没有设置，则为零（false），如果有任何设置，则为非零（true）。

- ephemient

1

我参加了 TI-89 BASIC 的速成课来解答这个问题 :)

让我们看看这个是否可行（我没有模拟器，所以无法检查）。

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

- Dr. belisarius

我不确定这是否正确，但是使用TI-basic值得赞扬 :p B - C -> B 看起来有点可疑。 - user166390

@pst 我同意，但我是通过示例学习的。请参阅此处的第一个代码块示例http://en.wikipedia.org/wiki/TI-BASIC :) - Dr. belisarius

我的意思是，我原本期望的是数字跳动会得到类似于 B / 10 -> B 的结果。 - user166390

@pst 需要比我更多的语言算术知识！你怎么知道它会返回一个整数？ - Dr. belisarius

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- paxdiablo · Accepted Answer

并不一定更快，但您仍应该进行测量，以防万一-我的优化口号是“测量，不要猜测”。

但我相信它的意图更清晰（而且足够简单，可以翻译成更简单的计算器语言）。它还能处理任意大小的整数。

int hasDupes (unsigned int n) {
    // Flag to indicate digit has been used, all zero to start.
    int used[10] = {0};

    // More than 10 digits must have duplicates, return true quickly.
    if (n > 9999999999) return 1;

    // Process each digit in number.
    while (n != 0) {
        // If duplicate, return true as soon as found.
        if (used[n%10]) return 1;

        // Otherwise, mark used, go to next digit.
        used[n%10] = 1;
        n /= 10;
    }

    // No duplicates after checking all digits, return false.
    return 0;
}

如果你的选择范围有限，你可以采用牺牲空间换取时间的传统方法。例如，假设你要处理0到999（包括）之间的数字（：标记只是为了缩小回答的大小而删除的数据）：

const int *hasDupes = {
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  //   0 -   9
        0, 1, 0, 0, 0, 0, 0, 0, 0, 0,  //  10 -  19
        0, 0, 1, 0, 0, 0, 0, 0, 0, 0,  //  20 -  29
                    :  :
        0, 0, 1, 0, 0, 1, 0, 0, 0, 0,  // 520 - 529
                    :  :
        0, 1, 0, 0, 0, 0, 0, 0, 1, 0,  // 810 - 819
                    :  :
        0, 0, 0, 0, 0, 0, 0, 1, 0, 1,  // 970 - 979
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1,  // 980 - 989
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  // 990 - 999
};

只需对hasDupes[n]进行表格查找。表本身可以通过编程生成（一次），然后插入到代码中供使用。

但是，根据您的编辑，在您需要处理九位数的情况下，十亿个元素的数组可能在您的计算器上不可行。因此，我建议选择第一种解决方案。