阵列作业问题 [英] Array Homework Question

问题描述

您将得到1到1,000,000之间的整数数组。一个整数数组中的两倍。你怎么能确定是哪一个？你能不能想办法用一些额外的内存来做到这一点。

算法中：

• 解决方案1：
    
  1. 有一个哈希表   
  2. 在遍历数组和存储其哈希表元素   
  3. 当你发现它已经在哈希表中的一个元素，它是DUP元素
  优点：
  • 在它运行在O（n）的时间，只有1通
  缺点：
  • 在它使用O（n）的额外内存

• 溶液2：
  1. 排序使用排序合并数组（O（nlogn）的时间）
  2. 重新解析，如果你看到两次的元素，你得到了DUP。
  优点：
  • 在不使用额外的内存
  缺点：
  • 在运行时间大于O（N）

你们能想到的任何更好的解决方案？

解决方案

现在的问题是有点含糊不清;当请求其中之一，它的意思是返回的值的被复制，或者是重复一个序列中的位置的？如果是前者，任何以下三种溶液的将工作;如果是后者，第一个是唯一的，这将有助于

解决方案1：假设数组是不可变

建立一个位图;设置的 N 的个位，你通过数组迭代。如果该位已经设置，你发现了一个重复。它运行在线性时间，并适用于任何大小的数组。

位图将与一样多的位创建为有数组中可能的值。当你通过数组迭代，你检查的 N 的次阵列中的位。如果它被设置，你发现你的副本。如果不是，则设置它。 （逻辑这样做可以在位阵列或本维基百科条目中可以看出，在伪code使用<一个href="http://msdn.microsoft.com/en-us/library/system.collections.bitarray.aspx">System.Collections.BitArray类。）

解决方案2：假设数组是可变

排序数组，然后做一个线性搜索，直到当前值等于previous值。使用最少内存中的所有的。奖励点数用于改变排序算法的比较操作期间检测到重复的和早期终止

解决方案3：（假设数组长度= 1,000,001）

1. 总和阵列中所有的整数。
2. 从说，减去整数1的总和，通过百万的包容性。
3. 什么是左将是您复制的价值。

这需要几乎没有额外的内存，可以一次完成，如果你计算在同一时间的总和。

缺点是，你需要做的整个循环中找到了答案。

的优点是简单和较高的概率它将实际上运行速度比其它解决方案。

You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one? Can you think of a way to do it using little extra memory.

Algo:

• Solution 1:
  1. Have a hash table
  2. Iterate through array and store its elements in hash table
  3. As soon as you find an element which is already in hash table, it is the dup element
  Pros:
  • It runs in O(n) time and with only 1 pass
  Cons:
  • It uses O(n) extra memory

• Solution2:
  1. Sort the array using merge sort (O(nlogn) time)
  2. Parse again and if you see a element twice you got the dup.
  Pros:
  • it doesn't use extra memory
  Cons:
  • Running time is greater than O(n)

Can you guys think of any better solution?

解决方案

The question is a little ambiguous; when the request is "which one," does it mean return the value that is duplicated, or the position in the sequence of the duplicated one? If the former, any of the following three solutions will work; if it is the latter, the first is the only that will help.

Solution #1: assumes array is immutable

Build a bitmap; set the nth bit as you iterate through the array. If the bit is already set, you've found a duplicate. It runs on linear time, and will work for any size array.

The bitmap would be created with as many bits as there are possible values in the array. As you iterate through the array, you check the nth bit in the array. If it is set, you've found your duplicate. If it isn't, then set it. (Logic for doing this can be seen in the pseudo-code in this Wikipedia entry on Bit arrays or use the System.Collections.BitArray class.)

Solution #2: assumes array is mutable

Sort the array, and then do a linear search until the current value equals the previous value. Uses the least memory of all. Bonus points for altering the sort algorithm to detect the duplicate during a comparison operation and terminating early.

Solution #3: (assumes array length = 1,000,001)

1. Sum all of the integers in the array.
2. From that, subtract the sum of the integers 1 through 1,000,000 inclusive.
3. What's left will be your duplicated value.

This take almost no extra memory, can be done in one pass if you calculate the sums at the same time.

The disadvantage is that you need to do the entire loop to find the answer.

The advantages are simplicity, and a high probability it will in fact run faster than the other solutions.

这篇关于阵列作业问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！