数组作业问题

给你一个整数在1到1000000之间的数组。 一个整数在数组中两次。 你怎么能确定哪一个? 你能想出一个方法来做一点点额外的记忆。

ALGO:

  • 解决scheme1:
    1. 有一个哈希表
    2. 遍历数组并将其元素存储在散列表中
    3. 只要你find一个已经在哈希表中的元素,它就是dup元素
      优点:
      • 它运行在O(n)时间,只有一次通过

      缺点:

      • 它使用O(n)额外的内存
  • 溶液2:
    1. 使用合并sorting(O(nlogn)时间)对数组进行sorting
    2. 再次parsing,如果你看到一个元素两次,你有dup。
      优点:
      • 它不使用额外的内存

      缺点:

      • 运行时间大于O(n)
  • 你们能想出更好的解决scheme吗?

    这个问题有点模棱两可。 当请求是“哪一个”时,是指返回重复的 ,还是重复序列中的位置 ? 如果前者,以下三种解决scheme中的任何一种都可以工作; 如果是后者,第一个是唯一有帮助的。

    解决scheme#1:假定数组是不可变的

    build立一个位图; 在迭代数组的时候设置第n位。 如果这个位已经被设置,你已经find了一个重复的。 它运行在线性时间,并将适用于任何大小的数组。

    位图将会创build与数组中可能的值一样多的位。 在遍历数组时,您检查数组中的第n位。 如果已设置,则已find您的副本。 如果不是,那就设置它。 (这样做的逻辑可以在位数组的维基百科条目中的伪代码中看到,也可以使用System.Collections.BitArray类。)

    解决scheme2:假定数组是可变的

    对数组进行sorting,然后进行线性search,直到当前值等于先前的值。 使用最less的记忆。 加分点改变sortingalgorithm以在比较操作期间检测到重复并提前终止。

    解决scheme#3 :(假定数组长度= 1,000,001)

    1. 总结数组中的所有整数。
    2. 从中减去1到1000000(含)的整数。
    3. 剩下的将是你的重复价值。

    这几乎不需要额外的内存,如果你同时计算总和,可以一次完成。

    缺点是你需要做整个循环才能find答案。

    其优点是简单,实际上运行速度比其他解决scheme高。

    假设所有从1到1,000,000的数字都在数组中 ,所有数字的总和为1到1,000,000是(1,000,000)*(1,000,000 + 1)/2 = 500,000 * 1,000,001 = 500,000,500,000

    所以把数组中的所有数字加起来,减去500,000,500,000,然后你会留下两次出现的数字。

    O(n)时间和O(1)存储器。

    如果假设不成立 ,可以尝试使用Bloom Filter–它们可以比散列表更紧凑地存储(因为它们只存储存在的事实),但是它们确实存在误报的风险。 这个风险可以通过我们select花费在Bloomfilter上的内存来决定。

    然后,我们可以使用布隆filter来检测O(n)时间中潜在的重复,并在O(n)时间内检查每个候选者。

    这个python代码是QuickSort的修改 :

     def findDuplicate(arr): orig_len = len(arr) if orig_len <= 1: return None pivot = arr.pop(0) greater = [i for i in arr if i > pivot] lesser = [i for i in arr if i < pivot] if len(greater) + len(lesser) != orig_len - 1: return pivot else: return findDuplicate(lesser) or findDuplicate(greater) 

    它在O(n logn)中find重复的,我想。 它在堆栈上使用额外的内存,但是它可以被重写为只使用原始数据的一个副本,我相信:

     def findDuplicate(arr): orig_len = len(arr) if orig_len <= 1: return None pivot = arr.pop(0) greater = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] > pivot] lesser = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] < pivot] if len(arr): return pivot else: return findDuplicate(lesser) or findDuplicate(greater) 

    产生越来越 的列表parsing会通过调用pop()来破坏原始数据。 如果arr在删除越来越 之后不是空的,那么必须有一个重复的并且必须是枢轴的

    代码遭受sorting数据通常的堆栈溢出问题,所以无论是随机数据还是迭代解决scheme都是必要的:

     def findDuplicate(full): import copy q = [full] while len(q): arr = copy.copy(q.pop(0)) orig_len = len(arr) if orig_len > 1: pivot = arr.pop(0) greater = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] > pivot] lesser = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] < pivot] if len(arr): return pivot else: q.append(greater) q.append(lesser) return None 

    但是,现在代码需要在循环顶部对数据进行深层复制,从而改变内存需求。

    这么多的计算机科学。 天真algorithm在python中将我的代码封装起来,可能是因为python的sortingalgorithm:

     def findDuplicate(arr): arr = sorted(arr) prev = arr.pop(0) for element in arr: if element == prev: return prev else: prev = element return None 

    我不build议对数组进行sorting然后检查,而是build议编写一个比较sorting函数的实现,只要finddup就退出,导致没有额外的内存要求(显然取决于您select的algorithm),最坏的情况O(nlogn)时间(同样取决于algorithm),而不是最好的(和平均值,取决于…)情况O(nlogn)时间。

    例如就地合并sorting的实现。

    http://en.wikipedia.org/wiki/Merge_sort

    提示:使用A XOR A == 0和0 XOR A == A的属性

    作为解决scheme(2)的一个变体,您可以使用基数sorting 。 没有额外的内存,并将运行在线性时间。 你可以争辩说时间也受到数字表示的大小的影响,但是你已经给出了这样的界限:基数sorting在时间O(kn)中运行,其中k是你可以对每一次传递进行sorting的数字的数量。 这使得整个algorithmO(7n)的sorting加上O(n)来检查重复的数字 – O(8n)= O(n)。

    优点:

    • 没有额外的记忆
    • 上)

    缺点:

    • 需要八个O(n)通行证。

    而如何find所有重复的问题? 这可以在小于O(n ln n)的时间内完成吗? (sorting和扫描)(如果你想恢复原始数组,在结束之后进行原始索引和重新sorting,这可以在O(n)时间完成)

     def singleton(array): return reduce(lambda x,y:x^y, array) 

    sorting整数sorting他们应该是他们的地方。 如果你发现“碰撞”,比find正确的号码。

    空间复杂度O(1)(只能覆盖相同的空间)时间复杂度小于O(n),因为你会统计发现碰撞在结束之前。