检查两个数字是否具有相同的数字。

Question

我需要编写一个程序，用于检查两个数字是否拥有相同的数字。

例如：

a = 4423, b = 2433;

尽管它们的数字出现次数不同，但它们具有相同的数字。

#include <stdio.h>
#include <stdlib.h>
int same_digit(int a, int b) {
  int n = abs(a), i;
  int count[10];
  for (i = 0; i < 10; ++i) {
    count[i] = 0;
  }
  while (n > 0) {
    count[n % 10]++;
    n = n / 10;
  }
  n = abs(b);
  while (n > 0) {
    count[n % 10]--;
    n = n / 10;
  }
  for (i = 0; i < 10; ++i)
    if (count[i] != 0)
      return 0;
  return 1;
}
int main() {
  int a, b;
  scanf("%d", &a);
  scanf("%d", &b);
  if (same_digit(a, b)) printf("Yes");
  else printf("No");
  return 0;
} 

我的代码问题在于它仅检查数字是否相同。我应该如何修改这个代码，使其在a中的所有数字都出现在b中，并且在b中的所有数字也都出现在a中，无论它们出现多少次，返回1。

- user17936437

---

将每个数字转换为出现的唯一数字的排序字符串。比较这两个字符串。调用一个函数两次以生成排序后的字符串。4233和2433都应该生成234，这将相等。 "排序"不是完整的快速排序 - 您有一个包含每个数字0..9计数的数组，并且您只需按顺序复制非零项到输出字符串即可。 - Jonathan Leffler

创建一个由10个元素组成的数组。对于第一个数字中找到的每个数字“i”，标记数组中的第“i”个元素。然后，对于在第二个数字中找到的每个数字，检查相应的数组元素是否被标记。 - Eugene Sh.

请注意我的下面的评论。Eugene Sh. 在他们的 评论中概述的算法检查第二个数字中的每个数字是否出现在第一个数字中，但不验证第一个数字中出现的每个数字是否出现在第二个数字中。如果两个数字分别是1234和123，则该算法会说“是”而不是“否”。 - Jonathan Leffler

@codproe 修复了我的错误代码。 - klutt

Answer 1

使用数组不是必需的，但它可以让代码更加清晰：

// Remove duplicate characters from sorted array
void remove_dups(char *str) 
{
    char *cur = str;
    while(*cur) 
    {
        *str = *cur;
        while(*++cur == *str);
        ++str;
    }
    *str = 0;
}

int cmp(const void *a, const void *b)
{
    return *(char*)a - *(char*)b;
}

int same_digit(int a, int b)
{
    char A[22], B[22]; // Room for 64 bit. Increase if necessary.
    char Aun[11], Bun[11]; // 10 digits
    
    sprintf(A, "%d", a);
    sprintf(B, "%d", b);
    
    qsort(A, strlen(A), sizeof *A, cmp);
    qsort(B, strlen(B), sizeof *B, cmp);
    
    remove_dups(A);
    remove_dups(B);

    return !strcmp(A, B);
}

演示

许多C语言编程人员可能会对此感到不满。这并非没有充分的理由。在Python或Javascript中，通常会以这种方式解决问题。如果您正在编写严肃的C代码，那么选择更高级别的语言可能是有原因的。而且很可能这些原因与C所能提供的性能有关。

然而，并没有任何阻止您从这里开始，稍后进行优化，当您确定该代码确实是瓶颈并使用性能分析仪时。而且谁知道呢？也许情况是这样更快。不要进行过早优化。

实际上，存在许多涉及数字的问题，如果您首先将数字转换为数字数组，则这些问题变得更加容易。而且，如果对数组进行排序，则许多涉及数组的问题变得更加容易。不要害怕将这种方法作为您的工具箱中的标准工具。

此外，对于未排序的数组，天真的解决方案通常是O(n²)，而对于已排序的数组，天真的解决方案只需O(n)。由于排序可以以O(n * log n)或更好的速度完成，因此您通常会得到相当不错的解决方案。当然，由于这种情况下的n通常小于10，因此天真的O(n²)可能更快。但是请记住，我相信您必须编写相当高级的代码才能在不使用数组的情况下以O(n * log n)解决此问题。如果有可能的话。（并不是说不可能。只是我不知道）

- klutt

---

非常简单的解决方案，很不错 :) 非常感谢。 - user17936437

这个程序如何处理其中一个数字有三个相同的数字，而另一个数字只有一个相同的数字（例如 111234 和 4321）？它们包含相同的数字，但生成的字符串不会相等。 - Jonathan Leffler

@JonathanLeffler 您说得完全正确。我误读了问题。我会在今天稍后修复它。 - klutt

Answer 2

一个由10个数字（或11个，如果我们想计算'-'符号）组成的直方图，每个频率都被限制在0和1之间，应该被实现为存储在整数中的位向量（位掩码）。然后，当然解决方案只能处理所有数字基础最多32个，但总体代码应该更加清晰、更小，而无需通过循环比较数组。

int hash_int(int b) {
    int hash = 0;
    // take abs as unsigned -- now 0 <= a <= 0x80000000u
    // unsigned mod 10 is btw more performant than signed mod
    unsigned int a = b >= 0 ? b : 0u - b;
    // construct the hash, removing duplicate digits as we go
    // performance wise `do {} while` is better than `while`
    // due to less jumping around - here the side effect is
    // that a==0 hashes to 1.
    // For comparison a==0 -> hash = 0 would work equally well
    do {
        hash |= 1 << (a % 10);
        a /= 10;
    } while (a);
    return hash;
}

bool is_same(int a, int b) { return hash_int(a) == hash_int(b); }

- Aki Suihkonen

---

顺便提一下，这种方法还适用于对超过每个数字1个元素的完整直方图进行计数以检查回文：考虑 uint64_t h = 0ull; do { h += 1ull << (4 * (a % 10)); } while (a /= 10); 在这里，可以计算15个相同的数字而不会溢出——12334的哈希值将是0x12110。 - Aki Suihkonen

Answer 3

你的代码比必要的复杂了一些。

只需为每个数字计算一个“有数字”的向量（例如，如果相应的数字在数字中，则每个元素为1）。这是一个直方图/频率表，除了数字的计数之外，它只是0或1。

然后，比较向量是否相等。

这里是一些重构后的代码：

#include <stdio.h>
#include <stdlib.h>

void
count(int x,int *hasdig)
{
    int dig;

    // handle negative numbers
    if (x < 0)
        x = -x;

    // special case for zero
    // NOTE: may not be necessary
#if 1
    if (x == 0)
        hasdig[0] = 1;
#endif

    for (;  x != 0;  x /= 10) {
        dig = x % 10;
        hasdig[dig] = 1;
    }
}

int
same_digit(int a, int b)
{
    int dig_a[10] = { 0 };
    int dig_b[10] = { 0 };
    int dig;
    int same = 1;

    count(a,dig_a);
    count(b,dig_b);

    for (dig = 0;  dig < 10;  ++dig) {
        same = (dig_a[dig] == dig_b[dig]);
        if (! same)
            break;
    }

    return same;
}

int
main()
{
    int a, b;

    scanf("%d", &a);
    scanf("%d", &b);

    if (same_digit(a, b))
        printf("Yes\n");
    else
        printf("No\n");

    return 0;
}

---

更新：

如果其中一个或两个数字是INT_MIN，请注意UB

是的，-INT_MIN仍然为负数:-(

我想出了另一种处理它的方法。然而，在我看来，几乎任何方法都似乎是额外的工作，只是为了使一个特殊情况起作用。因此，我保留了上面原始的[更快/更简单]代码。

而且，我添加了一些额外的测试/调试代码。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int opt_t;

void
count(int x,int *hasdig)
{
    int dig;

    // handle negative numbers
    if (x < 0)
        x = -x;

    // special case for zero
    // NOTE: may not be necessary
#if 1
    if (x == 0)
        hasdig[0] = 1;
#endif

    for (;  x != 0;  x /= 10) {
        dig = x % 10;

        // my -INT_MIN fix ...
        if (dig < 0)
            dig = -dig;

        hasdig[dig] = 1;
    }
}

int
same_digit(int a, int b)
{
    int dig_a[10] = { 0 };
    int dig_b[10] = { 0 };
    int dig;
    int same = 1;

    count(a,dig_a);
    count(b,dig_b);

    for (dig = 0;  dig < 10;  ++dig) {
        same = (dig_a[dig] == dig_b[dig]);
        if (! same)
            break;
    }

    return same;
}

void
dotest(int a,int b)
{

    printf("a=%d b=%d -- %s\n",
        a,b,same_digit(a,b) ? "Yes" : "No");
}

int
main(int argc,char **argv)
{
    char *cp;

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        cp = *argv;
        if (*cp != '-')
            break;

        if ((cp[1] == '-') && (cp[2] == 0)) {
            --argc;
            ++argv;
            break;
        }

        cp += 2;
        switch(cp[-1]) {
        case 't':
            opt_t = ! opt_t;
            break;
        }
    }

    do {
        int a, b;

        if (opt_t) {
            dotest(4423,2433);
            dotest(INT_MIN,1234678);
            dotest(INT_MIN,INT_MIN);
            dotest(INT_MAX,INT_MAX);
            break;
        }

        if (argc > 0) {
            for (;  argc > 0;  --argc, ++argv) {
                cp = *argv;
                if (sscanf(cp,"%d,%d",&a,&b) != 2)
                    break;
                dotest(a,b);
            }
            break;
        }

        scanf("%d", &a);
        scanf("%d", &b);
        dotest(a,b);
    } while (0);

    return 0;
}

- Craig Estey

---

这是一个 do { … } while (…); 循环很好用的时候： do { dig = x % 10; hasdig[dig] = 1; x /= 10; } while (x > 0); — 然后你就不需要 #if/#endif 代码了。当然，你也可以使用：do { dig = x % 10; hasdig[dig] = 1; } while ((x /= 10) > 0);，甚至可以使用：`do { hasdig[x % 10] = 1; } while ((x /= 10) > 0); —— 编程高尔夫！ - Jonathan Leffler

如果其中一个或两个数字是INT_MIN，请注意UB。解决这个问题最简单的方法是使用：if (x > 0) x = -x; 确保值为负数，然后在循环中使用 hasdig[-(x % 10)] = 1;。在2的补码系统中，如果%运算符的左侧为负数且右侧为正数，则结果为负数，因此这种方法是可行的。它之所以有效，是因为-INT_MAX可以表示为int，但-INT_MIN不能（同样，在2的补码系统中）。 - Jonathan Leffler

@JonathanLeffler 个人而言，我只在宏中使用 do { } while (0)，并将其作为驯服冗长的 if/else 嵌套的技巧。感谢您提醒 INT_MIN 的问题。我已经在一个未发布的新版本中测试过了 - 它通过了。在看到您的评论后，我重新测试了一下，并在同时使用 INT_MIN 的两个参数时得到了 UB/segfault。我保留了 dig = x % 10;，最初只是为了教学目的。现在我的 [不同的] INT_MIN 修复需要它。由于循环内的否定是有条件的，所以它可能比您的解决方案慢，但我还是想试一试。虽然，我认为 -O2 可以消除分支。 - Craig Estey

Answer 4

你需要存储两个数字中出现的数字。例如，对于这两个数字，你可以定义一个由10个bool元素组成的数组，其中第一个元素指定数字0是否出现，第二个元素指定数字1是否出现，以此类推。由于你需要两个这样的数组，因此你可以创建一个由2个这些数组组成的数组，从而得到一个二维数组。这样，你就可以在同一个循环中处理这两个数组。

在填充了这两个数组之后，你可以比较它们，以确定这两个数字是否使用相同的数字。

另外，将same_digit的返回类型更改为bool可能会更好。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool same_digit( int a, int b )
{
    int numbers[2] = { a, b };
    bool occurred[2][10] = { {false} };

    //determine which digits are used by the individual numbers
    //and fill the two arrays accordingly
    for ( int i = 0; i < 2; i++ )
    {
        int n = abs( numbers[i] );

        while ( n > 0 )
        {
            occurred[i][n%10] = true;
            n = n / 10;
        }
    }

    //determine whether both numbers use the same digits
    for ( int i = 0; i < 10; i++ )
        if ( occurred[0][i] != occurred[1][i] )
            return false;

    return true;
}

//the following code has not been modified
int main() {
  int a, b;
  scanf("%d", &a);
  scanf("%d", &b);
  if (same_digit(a, b)) printf("Yes");
  else printf("No");
  return 0;
}

- Andreas Wenzel

---

不需要有两个数组。当遍历第二个数字时，可以检查从第一个数字得到的数组。 - Eugene Sh.

你需要检查一下，@EugeneSh，确保第一个数字中的每个数字都出现在第二个数字中，并且第二个数字中的每个数字也都出现在第一个数字中。如果不小心的话，你可能会得到第一个数字为1234，第二个数字为123的情况，第二个数字中的每个数字都出现在第一个数字中，但是数字4没有出现在第二个数字里。 - Jonathan Leffler

@JonathanLeffler 啊，是的，这是我没有考虑到的微妙之处。 - Eugene Sh.

Answer 5

这是一个更简单的版本，适用于所有int值，包括INT_MIN的解决方案：

#include <stdlib.h>

int digit_set(int a) {
    int set = 0;
    // construct the set, one bit per digit value.
    // do / while allows for digit_set(0) = 1
    // integer division truncates towards 0 so the
    // remainder is the negative value of the low digit
    // hence abs(a % 10) is the digit value.
    // this works for all values including INT_MIN
    do {
        set |= 1 << abs(a % 10);
    } while ((a /= 10) != 0);

    return set;
}

bool same_digits(int a, int b) { return digit_set(a) == digit_set(b); }

- chqrlie

---

我自作主张地正确拼写了我的名字。 如果将abs操作执行O(log N)次与O(1)次相比较，这会有一些主观性，因为哪种方法更简单并不确定... - Aki Suihkonen

@AkiSuihkonen：抱歉打错字了，源代码更简单，并且正确处理INT_MIN。关于性能，abs()通常会被扩展为无分支代码，并且在x86_64上，模数和除以10的编译结果是单个乘法和一些移位操作，可以在Godbolt Compiler Explorer上看到。 - chqrlie