当前位置：文江博客话题详情

一种检查 num1 的数字是否是 num2 中的数字而不检查每个数字的方法？

发布于 2024-07-14 02:22:55 字数 596 浏览 5 评论 0原文

假设我猜到了彩票号码：

1689

而彩票的运作方式是，数字的顺序并不重要，只要数字与实际中奖彩票号码中的数字1:1匹配即可。

因此，数字 1689 将是一个中奖彩票号码：

1896、1698、9816 等。

只要您猜测的每一位数字都出现在目标号码中，那么您就中奖了。

有什么数学方法可以做到这一点吗？

我通过 O(N^2) 循环检查每个数字与中奖彩票号码的每个数字（用模数将它们分开）解决了这个问题。这很好，它有效，但我想知道是否有任何巧妙的数学技巧我可以做。

例如，一开始......我认为我可能会很棘手，只需取两个数字中每个数字的总和和乘积，如果它们匹配，那么你就赢了。

^ 你认为这可行吗？

~~但是，当我发现彩票猜测时，我很快就反驳了这一点：222 和 124 的数字不同，但乘积和和相同。~~

任何人都知道我可以使用的任何数学技巧来快速确定中的数字是否相同num1 与 num2 中的数字匹配，无论顺序如何？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

ぃ弥猫深巷。 2024-07-21 02:22:58

一个可爱的解决方案是使用 Zobrist 哈希的变体。（是的，我知道这有点矫枉过正，而且是概率性的，但是嘿，它很“聪明”。）

将一个十元素数组 a[0..9] 初始化为随机整数。然后，对于每个数字 d[]，计算 a[d[i]] 的总和。如果数字包含相同的数字，则结果相等； 概率很高（大约有多少个可能的整数），反之亦然。

（如果你知道总共最多有 10 位数字，那么你可以使用固定数字 1, 10, 100, ... 而不是随机数来保证成功。这就是没有太多伪装的桶排序。）

回复收藏 0 原文

梦中的蝴蝶 2024-07-21 02:22:57

如果 N 可以变得很大，那么对数字进行排序就是答案。

因为数字是 0..9，所以您可以计算数组 [0..9] 中彩票答案的每个数字出现的次数。

为了进行比较，您可以为猜测中遇到的每个数字减去 1。当你遇到计数已经为 0 的数字时，你就知道猜测是不同的。当你猜完所有数字时，猜测的数字是相同的（只要猜测的数字与彩票答案的数字一样多）。

回复收藏 0 原文

微凉徒眸意 2024-07-21 02:22:57

对于每个数字 d 乘以第 (d+1) 个素数。

这比排序或桶方法更数学化，但效率较低。其实就是变相的桶法。

回复收藏 0 原文

苦笑流年记忆 2024-07-21 02:22:57

我会对两个数字的数字进行排序并进行比较。

回复收藏 0 原文

冷心人i 2024-07-21 02:22:57

如果您只处理 4 位数字，我认为您不必过多考虑使用哪种算法。它们的表现大致相同。

而且 222 和 124 的和也不相同

回复收藏 0 原文

情感失落者 2024-07-21 02:22:57

你必须考虑到，当 n 很小时，效率的顺序无关紧要，并且常数开始变得更重要。你的数字实际上能达到多大？你能得到最多10位数字吗？ 20？ 100？如果你的数字只有几位数字，n^2 确实还不错。如果您有数千位数字的字符串，那么您实际上可能需要做一些更聪明的事情，例如排序或存储桶。（即计算 0、计算 1 等）

回复收藏 0 原文

山川志 2024-07-21 02:22:57

我从 Yuliy 那里偷了答案，starblue（给他们投票）

除了 O(1)

lottonumbers == mynumbers;

排序之外，分桶是最快的排序是 O(nlog2n)

Bucketsort 是一种 O(n) 算法。

因此，您需要做的就是执行两次（一次针对您的数字，一次针对目标集），如果数字相加，则它们匹配。
任何类型的排序都会增加开销，在这种情况下是不必要的。

array[10] digits;
while(targetnum > 0)
{
    short currDig = targetnum % 10;
    digits[currDig]++;
    targetnum = targetnum / 10;
}
while(mynum > 0)
{
    short myDig = mynum % 10;
    digits[myDig]--;
    mynum = mynum / 10;
}
for(int i = 0; i < 10; i++)
{
   if(digits[i] == 0)
      continue;
   else
     //FAIL TO MATCH
}

我承认这不是最漂亮的代码。

I'm stealing the answer from Yuliy, and starblue (upvote them)

Bucketing is the fastest aside from the O(1)

lottonumbers == mynumbers;

Sorting is O(nlog2n)

Bucketsort is an O(n) algorithm.

So all you need to do is do it twice (once for your numbers, once for the target-set), and if the numbers of the digits add up, then they match.
Any kind of sorting is an added overhead that is unnecessary in this case.

array[10] digits;
while(targetnum > 0)
{
    short currDig = targetnum % 10;
    digits[currDig]++;
    targetnum = targetnum / 10;
}
while(mynum > 0)
{
    short myDig = mynum % 10;
    digits[myDig]--;
    mynum = mynum / 10;
}
for(int i = 0; i < 10; i++)
{
   if(digits[i] == 0)
      continue;
   else
     //FAIL TO MATCH
}

Not the prettiest code, I'll admit.

回复收藏 0 原文

孤独岁月 2024-07-21 02:22:57

创建一个包含 10 个下标为 [0 .. 9] 的整数的数组。

将每个元素初始化为不同的素数

将乘积设置为 1。

使用数字中的每个数字作为数组的下标，
取出质数，然后乘以它的乘积。

这为您提供了与数字顺序无关的独特表示。

对其他号码执行相同的过程。

如果唯一的表示匹配，则原始数字匹配。

回复收藏 0 原文

囍笑 2024-07-21 02:22:57

如果不允许重复数字（但不确定是否是这种情况），则使用 10 位二进制数。最高有效位代表数字 9，LSB 代表数字 0。依次处理每个数字，并翻转找到的每个数字的相应位。

因此 1689 将是：1101000010，9816

也将是：1101000010，

然后进行 XOR 或如果你是赢家，则减法将留下 0

这只是分桶的简单形式

回复收藏 0 原文

甜味超标? 2024-07-21 02:22:57

只是为了好玩，并以正常的方式思考，而不是排序和其他方式，而是进行删除操作。如果结果字符串为空，则您获胜！

    Dim ticket As String = "1324"
    Dim WinningNumber As String = "4321"

    For Each s As String In WinningNumber.ToCharArray
        ticket = Replace(ticket, s, "", 1, 1)
    Next

    If ticket = "" Then MsgBox("WINNER!")
    If ticket.Length=1 then msgbox "Close but no cigar!"

这也适用于重复数字。

Just for fun, and thinking outside of the normal, instead of sorting and other ways, do the deletion-thing. If resultstring is empty, you have a winner!

    Dim ticket As String = "1324"
    Dim WinningNumber As String = "4321"

    For Each s As String In WinningNumber.ToCharArray
        ticket = Replace(ticket, s, "", 1, 1)
    Next

    If ticket = "" Then MsgBox("WINNER!")
    If ticket.Length=1 then msgbox "Close but no cigar!"

This works with repeating numbers too..

回复收藏 0 原文

乖乖兔^ω^ 2024-07-21 02:22:57

在存储数字之前对数字进行排序。在那之后，你们的数字将相等。

回复收藏 0 原文

爱的十字路口 2024-07-21 02:22:56

遍历每个数字，并计算每个数字出现的次数（放入两个不同的 10 元素数组）怎么样？完成总计后，比较每个数字的计数。由于您只查看每个数字一次，因此时间复杂度为 O(N)。

代码看起来像这样：

for(int i=0; i<digit_count; i++)
{
   guessCounts[guessDigits[i] - '0']++;
   actualCounts[actualDigits[i] - '0']++;
}

bool winner = true;
for(int i=0; i<10 && winner; i++)
{
   winner &= guessCounts[i] == actualCounts[i];
}

上面的代码假设guessDigits和actualDigits都是char字符串；如果它们包含实际数字，那么您可以跳过 - '0' 业务。

可能有一些优化可以减少占用空间或更快终止，但这是 O(N) 方法的一个非常简单的示例。

顺便说一句，正如我在评论中提到的，由于零，乘法/求和比较肯定不起作用。考虑 0123 和 0222。两种情况下乘积均为 0，总和均为 6。

How about going through each number, and counting up the number of appearances of each digit (into two different 10 element arrays)? After you'd done the totaling, compare the counts of each digit. Since you only look at each digit once, that's O(N).

Code would look something like:

for(int i=0; i<digit_count; i++)
{
   guessCounts[guessDigits[i] - '0']++;
   actualCounts[actualDigits[i] - '0']++;
}

bool winner = true;
for(int i=0; i<10 && winner; i++)
{
   winner &= guessCounts[i] == actualCounts[i];
}

Above code makes the assumption that guessDigits and actualDigits are both char strings; if they held the actual digits then you can just skip the - '0' business.

There are probably optimizations that would make this take less space or terminate sooner, but it's a pretty straightforward example of an O(N) approach.

By the way, as I mentioned in a comment, the multiplication/sum comparison will definitely not work because of zeros. Consider 0123 and 0222. Product is 0, sum is 6 in both cases.

回复收藏 0 原文