在列表中查找多个可能的重复整数中的任何一个 [英] Find any one of multiple possible repeated integers in a list

问题描述

给定一个 n+1 整数数组，每个整数都在 1 到 n 范围内，找到一个重复的整数.

Given an array of n+1 integers, each in the range 1 to n, find an integer that is repeated.

我在一次工作面试中被问到这个问题.这是我的答案:鸽巢原则说必须重复.我尝试使用二进制搜索方法，所以我在 Matlab 中做了这个，因为我知道:

I was asked this at a job interview. Here's my answer: The Pigeonhole Principle says there has to be a repeat. I tried to use a binary search approach, so I did this in Matlab, because that's what I know:

top = 0;
bot = 0;
for i=1:n+1
  if P[i] > n/2 
    top = top+1;
  else
    bot = bot+1;
end

那么我认为其中一个，top 或 bot，必须再次比 PhP 的 n/2 大.取那个范围并重复.

So then I argue that one of these, top or bot, has to be bigger than n/2 by the PhP again. Take that range and repeat.

我认为这是一个很好的解决方案，但面试官有点暗示可以做得更好.请发布您知道的任何更好的解决方案.

I thought this was a pretty good solution, but the interviewer sort of hinted that one can do better. Please post any better solutions you know of.

推荐答案

我不确定您如何定义更好"，但也许这符合条件.至少它不同于您的解决方案和链表问题的解决方案(双关语).

I'm not sure how you're defining "better", but perhaps this qualifies. At least it's different from your solution and the solutions to the linked list questions (pun intended).

如果我们创建路径

n+1 --> array[n+1] --> array[array[n+1]] --> ...

那么这个路径包含一个循环当且仅当 array^k[n+1] = array^l[n+1] for some k != l，即当且仅当存在重复时.这个问题现在变成了一个常见的链表问题，可以如下解决.

then this path contains a cycle if and only if array^k[n+1] = array^l[n+1] for some k != l, that is, if and only if there is a repeat. The question now becomes a common linked list problem that can be solved as follows.

在第一个节点上启动两个粒子.让第一个粒子以单位速度运动，让第二个粒子以两倍单位速度运动.然后如果有一个循环，第二个粒子最终会在第一个粒子后面循环，最终它们会是一样的.为什么?好吧，如果你把粒子想象成一个圆圈(一旦找到循环，它们就会成为圆圈)，那么在每个时间单位，第二个粒子都会更接近第一个粒子.因此它们最终必然会发生碰撞.他们做的一个，你发现了一个循环.要找到重复值，只需让一个粒子静止，而另一个粒子再次运行循环，即可得到循环的长度.然后在开始处重新启动两个粒子，让一个向前移动循环的长度，然后将两个粒子一起运行，它们之间的距离不变，直到它们在循环开始处再次相遇.

Start two particles on the first node. Let the first particle move at unit speed and let the second particle move at twice unit speed. Then if there is a cycle, the second particle will end up looping back behind the first, and eventually they'll be the same. Why? Well, if you think of the particles as on a circle (which they will be once the find the loop), at every time unit the second particle gets one directed step closer to the first. Therefore they must eventually collide. One they do, you've found a loop. To find the repeated value, simply get the length of the loop by letting one particle stand still while the other runs the loop again. Then start both particles at the start again, let one move the length of the loop ahead, and then run both particles together with constant distance between them until they meet again at the beginning of the loop.

由于一些评论员对我没有包含有关如何在链表中查找循环的所有细节感到愤怒，现在就在这里.不能保证这不是错误(毕竟它是 Matlab 式的伪代码)，但它至少应该解释这个想法.

As some commentators are outraged that I did not include all of the details of how to find a loop in a linked list, here it now is. No promises that this isn't buggy (it's Matlab-esque pseudocode after all), but it should at least explain the idea.

%% STEP 1: find a point in the cycle of the linked list using a slow and fast particle
slow = n+1;
fast = n+1;
for i=1 to n+1
    slow = array[slow];
    fast = array[array[fast]];
    if (slow == fast)
        break;
end

%% STEP 2: find the length of the cycle by holding one particle fixed
length = 1;
fast = array[fast]
while fast != slow
    fast = array[fast];
    length = length+1;
end

%% STEP 3: find the repeated element by maintaining constant distance between particles
slow = n+1;
fast = n+1;
for i=1 to length
    fast = array[fast];
end
while fast != slow
    fast = array[fast];
    slow = array[slow];
end

%% STEP 4: return the repeated entry
return slow;

这里我从 n+1 开始，因为 array[i] 介于 1 和 n 之间，所以两个粒子都不会被送回 n+1.这使得最多一次通过数组(尽管不是按顺序)并跟踪两个粒子(慢速和快速)和一个整数(长度).因此空间是O(1)，时间是O(n).

Here I started at n+1 because array[i] is between 1 and n, so neither particle will ever be sent back to n+1. This makes at most one pass through the array (though not in order) and keeps track of two particles (slow and fast) and one integer (length). The space is therefore O(1) and the time is O(n).

这篇关于在列表中查找多个可能的重复整数中的任何一个的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！