检查两个数字是否相互排列？

Question

给定两个数字a,b使得1 <= a,b <= 10000000000(10 ^ 10).我的问题是检查它们中的数字是否是彼此的排列.这样做的最快方法是什么？我想到使用散列但无法找到任何合适的散列函数.有什么建议？

例如 - 123是312的有效排列

另外,我不想对数字中的数字进行排序.

Answer 1

如果你的意思是数字的字符(例如1927和9721),那么(至少)有两种方法.

如果允许排序,一种方法是将sprintf它们简单地分配给两个缓冲区,对缓冲区中的字符进行排序,然后查看字符串是否相等.

然而,考虑到您的愿望,不是数字排序,另一种选择是设立一个十元数组,初始设置为零的所有元素,然后处理在第一个号码每个数字,增加相关的元素.

然后使用第二个数字执行相同操作但递减.

如果,最后,它仍然全部为零,则数字是彼此的排列.

这是有效的,因为它是一种O(n)算法,其中n是两个数字中的位数.这种野兽的伪代码如下:

def arePermutations (num1, num2):
    create array count, ten elements, all zero.
    for each digit in num1:
        increment count[digit]
    for each digit in num2:
        decrement count[digit]
    for each item in count:
        if item is non-zero:
            return false
    return true

在C中,以下完整程序说明了如何完成此操作:

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

#define FALSE (1==0)
#define TRUE  (1==1)

int hasSameDigits (long num1, long num2) {
    int digits[10];
    int i;

    for (i = 0; i < 10; i++)      // Init all counts to zero.
        digits[i] = 0;

    while (num1 != 0) {           // Process all digits.
        digits[num1%10]++;        // Increment for least significant digit.
        num1 /= 10;               // Get next digit in sequence.
    }

    while (num2 != 0) {           // Same for num2 except decrement.
        digits[num2%10]--;
        num2 /= 10;
    }

    for (i = 0; i < 10; i++)
        if (digits[i] != 0)       // Any count different, not a permutation.
            return FALSE;

    return TRUE;                  // All count identical, was a permutation.
}

 

int main (int c, char *v[]) {
    long v1, v2;

    if (c != 3) {
        printf ("Usage: %s <number1> <number2>\n", v[0]);
        return 1;
    }

    v1 = atol (v[1]);
    v2 = atol (v[2]);
    if (hasSameDigits (v1, v2)) {
        printf ("%d and %d are permutations\n", v1, v2);
    } else {
        printf ("%d and %d are not permutations\n", v1, v2);
    }

    return 0;
}

简单地传递两个(正数)数字,假设它们适合a long,它会告诉你它们是否具有相同的数字计数.

Answer 2

a和b是anagrams,如果它们具有相同数量的每个数字.所以基本上最快的方式似乎是,计算a和b的数字:

int c[10]={0,0,0,0,0,0,0,0,0,0}

while (a) { c[a%10]++; a/=10; }
while (b) { c[b%10]--; b/=10; }

int res=1;
for (int i=0;i<10;i++) res &= c[i]==0;
printf(res?"yes":"no");