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

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 中，并且来自 [=18] 的所有数字，我如何将此代码修改为 return 1 =]b 出现在 a 中，无论出现多少次。

Answer 1

您的代码有点复杂。

只需为每个数字计算一个“有一个数字”的向量（例如，如果相应数字在数字中，则每个元素为 1）。这是一个 histogram/frequency table 除了不是数字中的数字计数，它只是 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;
}

更新：

Also beware UB if either or both numbers is INT_MIN

是的，-INT_MIN是仍然是负面的:-(

我想出了另一种方法来处理它。然而，IMO，[几乎]任何方法似乎都是额外的工作，只是为了让一个特例起作用。所以，我保留了 [faster/simpler] 上面的原始代码

而且，我添加了一些额外的 test/debug 代码。

#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;
}

Answer 2

您需要存储两个数字中出现的数字。例如，对于这两个数字，您可以定义一个包含 10 个 bool 元素的数组，其中第一个元素指定数字 0 是否出现，第二个元素是否出现数字 1，等等. 因为你需要两个这样的数组，你可以制作一个包含 2 个这样的数组的数组，给你一个二维数组。这样，您就可以在同一个循环中处理两个数组。

两个数组都填完后，你可以比较它们，以确定两个数字是否使用相同的数字。

此外，将same_digit的return类型改为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;
}

Answer 3

不需要使用数组，但它肯定会成为干净的代码：

// 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);
}

Demo

许多 C 程序员会对此皱眉。这并非完全没有充分的理由。这就是您通常在 Python 或 Javascript 中解决问题的方式。如果您正在编写严肃的 C 代码，您可能有理由不选择更高级的语言。这些原因很可能与 C 可以提供的性能有关。

但是，当您断定此代码确实是分析器的瓶颈时，绝对没有什么可以阻止您从这里开始并稍后对其进行优化。谁知道呢？可能是这样更快。不要过早优化。

实际上有很多涉及数字的问题，如果您先将数字转换为数字数组，这些问题就会变得容易得多。如果对数组进行排序，许多涉及数组的问题就会变得容易得多。不要害怕将此方法作为您工具箱中的标准工具。

此外，很常见的是，未排序数组的简单解决方案是 O(n²)，而排序数组的简单解决方案仅为 O(n)。由于排序可以在 O(n * log n) 或更短的时间内完成，因此您通常会得到一个很好的解决方案。当然，因为在这种情况下 n 通常小于 10，所以天真的 O(n²) 可能无论如何都更快。但值得记住。我相信您必须编写漂亮的代码才能在没有数组的情况下在 O(n * log n) 中解决这个问题。如果可能的话。（不是说不可能，只是不知道）

Answer 4

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); }

Answer 5

这是 Aki Suihkonen 解决方案的一个更简单版本，适用于所有 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); }

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

Check if two numbers have same digits

c

integer