算法来确定阵列包含n个... N + M？ [英] Algorithm to determine if array contains n...n+m?

问题描述

我看到在Reddit上这个问题，并没有正解presented，而且我认为这将是一个完美的问题要问在这里。这是在一个线程关于面试问题：

  

写方法，它的大小为m的int阵列，和返回（真/假）如果数组由号n ... N + M-1，在此范围内的所有数字和只有数字在该范围内。该阵列不保证进行排序。 （例如，{2,3,4}会返回true。{1,3,1}将返回false，{1,2,4}将返回false。

     

我有这一个问题是，我的面试官一直问我，优化（更快的为O（n），更少的内存等），到了那里，他声称你可以用做一个合格的数组点一定量的内存。从来没有计算过，一出。

随着您的解决方案，请注明，如果他们假设数组包含独特的项目。同时指出，如果你的解决方案假定顺序为1开始（我修改的问题稍微允许的情况下，哪里就有奇迹2，3，4 ...）

编辑：我现在不存在于时间的线性和空间的算法处理重复不变的观点是。任何人都可以验证这一点？

重复的问题归结为测试，看看如果数组包含为O重复（n）时间，O（1）空间。如果可以做到这一点就可以简单地测试第一和如果没有重复运行张贴的算法。所以你能在O测试的易受骗的人（n）时间O（1）空间？

解决方案

在假设的数字少于一不允许和有没有重复，有一个简单求和身份为此 - 号码从<$ c中的总和$ C> 1 到 M ，增量 1 是 （M *（M + 1））/ 2 。然后，您可以总结的数组，并使用该标识。

您可以找出是否有在上述担保一个傻瓜，再加上保证没有数超过米或小于n（可以在 O（N检查））

在伪code的想法：
  0）开始在N = 0
  1）取列表中的第N个元素。
  2）如果不是在如果列表已经排序的正确的地方，检查它应该是。
  3）如果它应该是已经在地方有相同的号码，你有一个傻瓜 - 返回true
  4）否则，交换数字（把第一个数字在正确的地方）。
  5）用你刚换的号码，它是在正确的地方？
  6）如果没有，返回到第二步。
  7）否则，就在步骤之一，N = N + 1。如果这将是过去的列表的末尾，你有没有愚弄。

和，是的，它运行在 O（N）尽管它可能看起来像 O（N ^ 2）

注意每个人（的东西从收集的意见）

此解决方案，您可以修改数组的假设下工作的，然后使用就地基数排序（其中达到 O（N）速度）。

其他mathy-解决方案已经提出，但我不知道任何人都得到了证明。有一堆总和可能有用的，但其中大多数的碰上在重新present的总和所需的比特的数量，这将违反恒定额外空间保证一个爆破。我也不知道，如果任何人都能够产生不同的号给定数的。我觉得平方和可能的工作，其中有一个已知的公式来计算（见 Wolfram的）

新见解（当然，更多的沉思中不帮助解决，但很有趣，我要去睡觉了）：

因此​​，已经提到也许使用平方和的总和+。没有人知道，如果这个工作还是没有，我意识到，这只是成为一个问题，当（X + Y）=（N + M），如事实2 + 2 = 1 + 3，广场也有这个问题，谢谢毕达哥拉斯三元（SO 3 ^ 2 + 4 ^ 2 + 25 ^ 2 = = 5 ^ 2 + 7 ^ 2 + 24 ^ 2，平方和不工作）。如果我们使用费马大定理，我们知道这是不可能发生的对n ^ 3。但是，我们也不知道有没有X + Y + Z = N这个（除非我们这样做，我不知道）。所以不能保证这一点，也不会破坏 - 而如果我们继续沿着这条道路，我们赶紧跑位了

在我的欢乐，但我忘了要注意的是，你可以打破平方和，但这样做，你创建一个正常的金额无效。我不认为你可以两者都做，但是，正如已经指出的，我们并没有证明任何一种方式。

---

我必须说，发现反例有时候比证明事情容易多了！考虑下面的序列，所有这些都具有28之和的140平方和

的 [1，2，3，4，5，6，7]
[1，1，4，5，5，6，7]
[2，2，3，3，4，7,7]
 

我找不到长度为6或更小的任何这样的例子。如果你想有适当的最小值和最大值过一个例子，试试这个一长度为8：

的 [1，3，3，4，4，5，8，8]
 

---

简单的方法（修改hazzen的想法）：

的长度为m的整数数组包含从n到N + M-1恰好一次所有数字IFF

• 在每个数组元素是n和N + M-1
之间
• 有没有重复

（原因：有在给定的整数的范围仅M值，所以如果数组包含在这个范围M唯一值，它必须包含他们每个人一次）

如果你被允许修改数组，你可以一次通过列表的hazzen算法的想法修改后的版本，同时检查（有没有必要做任何总和）：

• 对于所有的数组索引我从0到M-1做
  1. 如果数组[1] - ; n或阵[I]> = N + M =>返回FALSE（值超出范围发现）
  2. 在计算J =数组[我] - N（这是数组的0开始的位置[I]中的排序的阵列从n到N + M-1的值）
  3. 虽然j不等于i
     1. 如果表[i]等于列出[J] =>返回FALSE（重复找到）
     2. 在交换名单[I]与列表[J]。
     3. 在重新计算J =数组[我] - N
• 返回true

我不知道，如果对最大原始数组计数的修改允许的O（1）额外的空间，但如果没有这应该是解决原来的海报通缉。

I saw this question on Reddit, and there were no positive solutions presented, and I thought it would be a perfect question to ask here. This was in a thread about interview questions:

Write a method that takes an int array of size m, and returns (True/False) if the array consists of the numbers n...n+m-1, all numbers in that range and only numbers in that range. The array is not guaranteed to be sorted. (For instance, {2,3,4} would return true. {1,3,1} would return false, {1,2,4} would return false.

The problem I had with this one is that my interviewer kept asking me to optimize (faster O(n), less memory, etc), to the point where he claimed you could do it in one pass of the array using a constant amount of memory. Never figured that one out.

Along with your solutions please indicate if they assume that the array contains unique items. Also indicate if your solution assumes the sequence starts at 1. (I've modified the question slightly to allow cases where it goes 2, 3, 4...)

edit: I am now of the opinion that there does not exist a linear in time and constant in space algorithm that handles duplicates. Can anyone verify this?

The duplicate problem boils down to testing to see if the array contains duplicates in O(n) time, O(1) space. If this can be done you can simply test first and if there are no duplicates run the algorithms posted. So can you test for dupes in O(n) time O(1) space?

解决方案

Under the assumption numbers less than one are not allowed and there are no duplicates, there is a simple summation identity for this - the sum of numbers from 1 to m in increments of 1 is (m * (m + 1)) / 2. You can then sum the array and use this identity.

You can find out if there is a dupe under the above guarantees, plus the guarantee no number is above m or less than n (which can be checked in O(N))

The idea in pseudo-code:
0) Start at N = 0
1) Take the N-th element in the list.
2) If it is not in the right place if the list had been sorted, check where it should be.
3) If the place where it should be already has the same number, you have a dupe - RETURN TRUE
4) Otherwise, swap the numbers (to put the first number in the right place).
5) With the number you just swapped with, is it in the right place?
6) If no, go back to step two.
7) Otherwise, start at step one with N = N + 1. If this would be past the end of the list, you have no dupes.

And, yes, that runs in O(N) although it may look like O(N ^ 2)

Note to everyone (stuff collected from comments)

This solution works under the assumption you can modify the array, then uses in-place Radix sort (which achieves O(N) speed).

Other mathy-solutions have been put forth, but I'm not sure any of them have been proved. There are a bunch of sums that might be useful, but most of them run into a blowup in the number of bits required to represent the sum, which will violate the constant extra space guarantee. I also don't know if any of them are capable of producing a distinct number for a given set of numbers. I think a sum of squares might work, which has a known formula to compute it (see Wolfram's)

New insight (well, more of musings that don't help solve it but are interesting and I'm going to bed):

So, it has been mentioned to maybe use sum + sum of squares. No one knew if this worked or not, and I realized that it only becomes an issue when (x + y) = (n + m), such as the fact 2 + 2 = 1 + 3. Squares also have this issue thanks to Pythagorean triples (so 3^2 + 4^2 + 25^2 == 5^2 + 7^2 + 24^2, and the sum of squares doesn't work). If we use Fermat's last theorem, we know this can't happen for n^3. But we also don't know if there is no x + y + z = n for this (unless we do and I don't know it). So no guarantee this, too, doesn't break - and if we continue down this path we quickly run out of bits.

In my glee, however, I forgot to note that you can break the sum of squares, but in doing so you create a normal sum that isn't valid. I don't think you can do both, but, as has been noted, we don't have a proof either way.

---

I must say, finding counterexamples is sometimes a lot easier than proving things! Consider the following sequences, all of which have a sum of 28 and a sum of squares of 140:

[1, 2, 3, 4, 5, 6, 7]
[1, 1, 4, 5, 5, 6, 6] 
[2, 2, 3, 3, 4, 7, 7]

I could not find any such examples of length 6 or less. If you want an example that has the proper min and max values too, try this one of length 8:

[1, 3, 3, 4, 4, 5, 8, 8]

---

Simpler approach (modifying hazzen's idea):

An integer array of length m contains all the numbers from n to n+m-1 exactly once iff

• every array element is between n and n+m-1
• there are no duplicates

(Reason: there are only m values in the given integer range, so if the array contains m unique values in this range, it must contain every one of them once)

If you are allowed to modify the array, you can check both in one pass through the list with a modified version of hazzen's algorithm idea (there is no need to do any summation):

• For all array indexes i from 0 to m-1 do
  1. If array[i] < n or array[i] >= n+m => RETURN FALSE ("value out of range found")
  2. Calculate j = array[i] - n (this is the 0-based position of array[i] in a sorted array with values from n to n+m-1)
  3. While j is not equal to i
     1. If list[i] is equal to list[j] => RETURN FALSE ("duplicate found")
     2. Swap list[i] with list[j]
     3. Recalculate j = array[i] - n

• RETURN TRUE

I'm not sure if the modification of the original array counts against the maximum allowed additional space of O(1), but if it doesn't this should be the solution the original poster wanted.

这篇关于算法来确定阵列包含n个... N + M？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！