数组作业问题

Question

您将获得一个整数介于1和1,000,000之间的数组.一个整数在数组中两次.你怎么决定哪一个？你能想到一种方法来使用额外的内存来做到这一点.

ALGO:

• 解决方案1:
  1. 有一个哈希表
  2. 迭代数组并将其元素存储在哈希表中
  3. 一旦找到已经在哈希表中的元素,它就是dup元素
  优点:
  • 它在O(n)时间运行,只有1次通过
  缺点:
  • 它使用O(n)额外的内存
• 溶液2:
  1. 使用合并排序(O(nlogn)时间)对数组进行排序
  2. 再次解析,如果你看到一个元素两次,你得到了dup.
  优点:
  • 它不使用额外的内存
  缺点:
  • 运行时间大于O(n)

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

Answer 1

问题有点含糊不清; 当请求是"哪一个"时,是否意味着返回重复的值,或重复的序列中的位置？如果是前者,以下三种解决方案中的任何一种都可以使用; 如果是后者,第一个是唯一有帮助的.

解决方案#1:假设数组是不可变的

构建位图; 在迭代数组时设置第n位.如果该位已设置,则表示您找到了重复项.它在线性时间运行,适用于任何大小的数组.

将使用与数组中可能的值一样多的位来创建位图.在迭代数组时,检查数组中的第n位.如果已设置,您已找到副本.如果不是,则设置它.(这样做的逻辑可以在比特阵列上的维基百科条目中的伪代码中看到,或者使用System.Collections.BitArray类.)

解决方案#2:假设数组是可变的

对数组进行排序,然后进行线性搜索,直到当前值等于先前的值.使用最少的记忆.用于改变排序算法以在比较操作期间检测重复并且提前终止的加值点.

解决方案#3 :(假设数组长度= 1,000,001)

1. 求和数组中的所有整数.
2. 从那里,减去1到1,000,000的整数之和.
3. 剩下的将是您的重复值.

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

缺点是你需要完成整个循环才能找到答案.

优点是简单,并且实际上它比其他解决方案运行得更快的可能性很高.

Answer 2

假设从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)记忆.

如果假设不成立,您可以尝试使用布隆过滤器 - 它们可以比哈希表更紧凑地存储(因为它们只存储存在的事实),但它们确实存在误报的风险.通过我们选择在布隆过滤器上花费多少内存,这种风险可能会受到限制.

然后我们可以使用布隆过滤器在O(n)时间内检测潜在的重复,并在O(n)时间内检查每个候选.

Answer 3

这个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)中找到了重复.它使用堆栈上的额外内存,但它可以重写为只使用原始数据的一个副本,我相信:

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)

通过调用pop()产生更大和更小的破坏原始的列表推导.如果arr在从中移除较大和较小之后不为空,则必须有重复且必须是枢轴.

代码在排序数据上遇到通常的堆栈溢出问题,因此需要随机数据透视或对数据进行排队的迭代解决方案:

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

但是,现在代码需要在循环顶部获取数据的深层副本,从而改变内存需求.

对计算机科学来说太过分了 天真算法在python中破坏了我的代码,可能是因为python的排序算法:

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