发现多种可能重复整数列表中的任一项 [英] Find any one of multiple possible repeated integers in a list

问题描述

鉴于 N + 1 整数范围内的 1 阵列，每到 ñ，找到一个整数是重复的。

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

于是我认为，其中的一个，顶或机器人，必须大于 N / 2 由PHP的了。采取这一范围和重复。

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.

我认为这是一个pretty的很好的解决方案，但排序的面试官暗示，人们可以做的更好。请张贴任何更好的解决方案，你知道的。

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]] --> ...

那么这个路径中包含一个周期，当且仅当阵列^ K表[N + 1] =阵列^ L [N + 1] 一些 K！=升，即，当且仅当有一个重复。现在的问题是，可以如下解决的一个常见链表问题

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的式的伪$毕竟C $ C），但它至少应该解释的想法。

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 ，因为数组[我] 为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屋！