检查两个数字是否是彼此的排列？ [英] Checking whether two numbers are permutation of each other?

问题描述

给定两个数的a，b，使得1所述; = A，B＆下; =百亿（10 ^ 10）。我的问题是，检查其中的数字是否相互与否的排列。什么是这样做的最快的方法？我使用散列，但无法找到任何合适的散列函数认为。有什么建议？

Given two numbers a, b such that 1 <= a , b <= 10000000000 (10^10). My problem is to check whether the digits in them are permutation of each other or not. What is the fastest way of doing it? I was thinks of using hashing but unable to find any suitable hash function. Any suggestions?

有关例如 -
    123是312的有效置换

For e.g - 123 is a valid permutation of 312

此外，我不希望在号码的数字进行排序。

推荐答案

如果你指的是数字的字符（如1927年和9721），有（至少）一对夫妇的方法。

If you mean the characters of the numbers (such as 1927 and 9721), there are (at least) a couple of approaches.

如果你被允许进行排序，一种方法是简单地的sprintf 他们两个缓冲区，缓冲区中的人物进行排序，然后看看如果字符串是相等的。

If you were allowed to sort, one approach is to simply sprintf them to two buffers, sort the characters in the buffers, then see if the strings are equal.

不过，鉴于你的愿望的不的数字进行排序，另一种选择是设立一个十元素数组，初始设置为零的所有元素，然后处理每个数字在第一个数字，递增的相关元素。

However, given your desire to not sort the digits, another alternative is to set up a ten-element array, with all elements initially set to zero, then process each digit in the first number, incrementing the relevant element.

然后做同样的与第二个号码，但递减。

Then do the same with the second number but decrementing.

如果，到了最后，它仍然是全零，这个数字是对方的一个排列。

If, at the end, it's still all zeros, the numbers were a permutation of each other.

这是有效的，因为它是一个 O（N）算法，其中 N 是在数字位数两个数字。伪code这样的兽会是这样的：

This is efficient in that it's an O(n) algorithm where n is the number of digits in the two numbers. The pseudo-code for such a beast would be something like:

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，下面的完整的程序说明了如何可以做到这一点：

In C, the following complete program illustrates how this can be done:

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

＆NBSP;

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

简单地传递两个（正）数量和，假设他们适合在长，它会告诉你他们是否有相同数字的计数。

Simply pass it two (positive) numbers and, assuming they fit in a long, it'll tell you whether they have the same digit counts.

这篇关于检查两个数字是否是彼此的排列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！