c++ - 检查两个数字是否互为排列？

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

只需将两个(正)数字传递给它，假设它们适合 long，它会告诉您它们是否具有相同的数字计数。