找到一个数字,精确显示n/2次

如果你准备好接受一个很小的错误概率,就有一个固定的时间解。从数组中随机抽取两个值,如果它们相同,则找到要查找的值。在每一步,你都有0.75的概率没有完成。因为每一个epsilon都有一个n,这样(3/4)^n<eps,我们最多可以采样n次,如果没有找到匹配的对,则返回一个错误。

还要注意,如果我们一直采样直到找到一对,那么预期的运行时间是恒定的,但是最坏的情况下运行时间是不受限制的。

下面是我的尝试,以证明为什么在小于O(n)数组访问中不能做到这一点(对于最坏的情况,这肯定是本例中唯一有趣的情况):

假设存在最坏情况日志(n)算法。该算法最多访问n次数组。因为它不能假设哪些元素在哪里,所以让我选择它所看到的哪些日志(n)元素。我将选择给它第一个日志(n)唯一元素。它还没有找到副本,并且仍然存在n/2-log(n)个唯一元素,如果需要,我可以将其提供给它。事实上,在它读取n/2元素之前,我不能强迫它输入一个重复的数字。因此,这种算法不可能存在。

从纯直觉的角度来看,这似乎是不可能的。对数(40亿)是32。因此,对于一个由40亿个数字组成的数组,其中20亿个是唯一的,没有特定的顺序,有一种方法可以通过只检查32个元素来找到重复的元素吗?

我认为您只需要通过数组进行解析,保留两个元素的积压。因为n/2是相等的,其余的保证是不同的,所以数组中必须有一个位置i,其中

a[i] == a[i-1] OR a[i] == a[i-2]

在数组中迭代一次,其复杂性大约为2*n,应该在o(n)内部。

这个答案有点像甘尼什M和道格的答案,但我觉得简单一点。

您不能在子行时间内这样做,因为您需要读取数组。要在对数时间内处理一百万条记录的数组,只需要读取~20(log2)个元素——显然是不可能的。毕竟,如果假设找到的第一个副本重复n/2次,那么它仍然是o(n),因为您可能需要查看500001个元素才能找到副本。

如果你假设整数是非负的,你可以用o(n)来做这个。它是这样的(伪Java):

int repeatedNumber = -1; // sentinel value
int count = 0;
BitSet bits = new BigSet(); // this bitset needs to have 2^31 bits, roughly 2.1 billion
boolean duplicate = false;
for (int i : elements) {
  if (bits[i].isSet()) {
    if (repeatedNumber == -1) {
      repeatedNumber = i;
      count = 1;
    } else if (i == repeatedNumber) {
      count++;
    } else {
      System.out.println("Array has more than one repeated element");
      duplicate = true;
      break;
    }
  } else {
    bits[i].set();
  }
}
if (!duplicate && repeatedNumber != -1 && count == elements.length/2) {
  System.out.println(repeatedNumber + " occurred " + count + " times. The rest of the elements are unique");
} else {
  System.out.println("Not true");
}

类似的方法用于对O(n)(基数排序)中的唯一整数数组进行排序。

最坏情况 确定性的 行为,O(N)是正确的(我已经在前面的答案中看到了不止一个证据)。

然而,现代算法理论不只是关注最坏情况的行为(这就是为什么除了big-o之外还有那么多其他大的东西,尽管懒惰的程序员在匆忙中经常使用big-o,即使他们的头脑中的东西更接近big the t a或big omega;-),也不只是关注确定性(与米勒-拉宾初等性测试…;)。

任何k<n项目的随机样本都不会显示任何重复,其可能性为<2**k——无论n是什么,都可以轻松快速地降低到您希望的最低水平(例如,您可以将其降低到低于随机宇宙射线意外和不可检测地在您的记忆中翻转一点的概率);—需要拉宾和米勒的创造力 他们的 概率素数检验法;-)。

这将是一个相当糟糕的面试问题。类似的不那么糟糕的问题经常被提出,经常回答错误, 和 往往被不成功的候选人忘记。例如,一个典型的问题可能是,给定一个n个项的数组, 不知道 是否有多数项,以确定在O(n)时间内是否有一个和它是哪个项。 和 o(1)辅助空间(因此您不能只设置哈希表或其他内容来计算不同值的出现次数)。摩尔的投票方法“是一个很好的解决办法(可能是最好的一个) 那个 值得面试的问题。

另一个有趣的变化:如果你有 10**18 64位数字(总价值8兆字节的数据,比如在一个大表或其克隆上),以及尽可能多的机器,每个机器在一个相当快的局域网上都有大约4GB的RAM,比如说一个比GB以太网好得多的机器——如何在 那些 条件?如果必须使用mapreduce/hadoop怎么办?如果您可以为这一个问题自由地设计自己的专用框架,那么您能获得比MapReduce更好的性能吗?在信封背面估计的粒度上有多好?我不知道这个变种的公开算法,所以如果你想用高度分布式的方法来检查一个候选者的一般功能,这可能是一个很好的测试。

我的答案是,

1. 将n个元素分为[n/3]个部分(即每个部分将有3个元素)。
2. 现在比较这三个元素。- 3个比较
3. 至少一个部件将具有同一元素的两个副本。这就是数字。

运行时-O(n)

彼得是对的。这里有一种更正式的方式来重申他的证据:

设为包含n个元素的集合。它是两个集合的并集:p,其中包含一个重复n/2次的符号α,q,其中包含n/2唯一符号ω。 _一 ..ω _N/2 . S=P q。

假设有一种算法可以在日志(n)比较中检测到重复的数字 最坏的情况下 所有N>2。在最坏的情况下意味着 不存在任何子集r s,因此r=log _二 n其中αr .

然而,由于S=P Q,S P=N/2中有P多个元素≠α,因此N/2使得N/2≥对数 _二 n,必须存在至少一个集合r s,以便r=log _二 n和αr。这是任何n≥3的情况。这与上述假设相矛盾,因此不存在任何此类算法。

QED。

要做到小于0(n),你就不必读所有的数字。
如果你知道有一个满足关系的值,那么你可以对一个小的子集进行抽样,显示只有一个数字出现足够的时间来满足关系。您必须假设这些值是合理均匀分布的

编辑。你必须读n/2来证明这样一个数字存在,但是如果你知道一个数字存在并且只想找到它,你可以读sqrt(n)样本。

答案很简单。并且可以在最坏情况下(n/2+1)进行比较

1. 比较成对的第一个(n-2)数字,即比较0和1的数字,然后比较2和3等等…总n/2-1比较。 如果我们在上面的比较中发现相同的数字……我们有重复的数字…其他:

2. 取最后两个剩余数字中的任意一个(比如我取的第二个最后一个),并将其与最后一对中的第二个数字进行比较。如果匹配发生..第二个最后一个号码是重新指定的号码,另一个最后一个号码是重复的号码…在所有两个比较中。

总比较=n/2-1+2=n/2+1(最坏情况) 我不认为有任何O(log n)方法可以实现这一点

很容易看出不存在O(log n)算法。显然,您必须查看数组元素以确定重复元素是哪个,但是无论您选择以何种顺序查看元素,您查看的第一层(n/2)元素都可能是唯一的。你可能只是不走运。如果发生这种情况,您将无法知道哪个是重复的元素。由于在每次运行中使用小于楼层(n/2)数组引用或更少的算法都不起作用,因此绝对没有亚线性算法。

如果我能正确理解这个问题:我们对数组的了解就是它的长度,它有(n/2)+1个唯一元素,其中1个元素重复n/2次(没有特定的顺序)。

我认为对于解决方案,这会受到O(n)的硬限制,因为您不能(对于泛型数组)断言在找到相同数字的至少2个之前找到了该数字。我不认为有一个搜索无序数组可以检测到在O(logn)中的重复(如果我错了,请纠正我)。在最坏的情况下,您总是需要读取至少n/2+1个元素。

将我的解决方案从注释重述到Ganesh的版本,这样我就可以对其进行格式化:

for (i=0; i<N-2; i+=3) { 
   if a[i] == a[1+1] || a[i] == a[i+2] return a[i];
   if a[i+1] == a[i+2] return a[i+1]; 
} 
return a[N-1]; // for very small N

一次迭代获胜概率:50%

2次迭代后获胜概率:75%

等。

最坏情况下,O(n)时间O(1)空间。

注意,在N/4迭代之后,您已经用完了所有的N/2唯一数字,因此如果指定了它,那么这个循环将永远不会迭代超过数组的3/4。

假设您有这样一个python算法:

import math
import random

def find_duplicate(arr, gap):
    cost, reps = 0, 0
    while True:
        indexes = sorted((random.randint(0,len(arr)-i-1) for i in xrange(gap)), reverse=True)
        selection = [arr.pop(i) for i in indexes]
        selection_set = set(selection)
        cost += len(selection)
        reps += 1
        if len(selection) > len(selection_set):
            return cost, reps

想法是 ARR 是你的一套价值观和 缺口 是大小的对数基数2。每次选择 缺口 元素,查看是否有重复的值。如果是这样,则返回您的成本(以检查的元素计数)和迭代次数(在这里,每次迭代检查log2(大小)元素)。否则,看看另一个 缺口 尺寸设定。

这个算法的标杆问题是,如果数据量很大,那么每次通过循环创建数据和更改数据都是很昂贵的。(最初,我用1000000次迭代做了1000000个元素。)

所以我们把它简化为一个等价的问题。数据作为n/2唯一元素和n/2重复元素传入。该算法选取log2(n)元素的随机索引,并检查是否重复。现在,我们甚至不必创建数据,也不必删除被检查的元素: 我们只需检查在中间点是否有两个或多个索引 . 选择 缺口 索引,检查中间点是否有2个或更多:如果找到则返回,否则重复。

import math
import random

def find_duplicate(total, half, gap):
    cost, reps = 0, 0
    while True:
        indexes = [random.randint(0,total-i-1) for i in range(gap)]
        cost += gap
        reps += 1
        above_half = [i for i in indexes if i >= half]
        if len(above_half) >= 2:
            return cost, reps
        else:
            total -= len(indexes)
            half -= (len(indexes) - len(above_half))

现在按如下方式驱动代码:

if __name__ == '__main__':
    import sys
    import collections
    import datetime
    for total in [2**i for i in range(5, 21)]:
        half = total // 2
        gap = int(math.ceil(math.log10(total) / math.log10(2)))
        d = collections.defaultdict(int)
        total_cost, total_reps = 0, 1000*1000*10
        s = datetime.datetime.now()
        for _ in xrange(total_reps):
            cost, reps = find_duplicate(total, half, gap)
            d[reps] += 1
            total_cost += cost
        e = datetime.datetime.now()
        print "Elapsed: ", (e - s)
        print "%d elements" % total
        print "block size %d (log of # elements)" % gap
        for k in sorted(d.keys()):
            print k, d[k]
        average_cost = float(total_cost) / float(total_reps)
        average_logs = average_cost / gap
        print "Total cost: ", total_cost
        print "Average cost in accesses: %f" % average_cost
        print "Average cost in logs: %f" % average_logs
        print

如果您尝试这个测试,您会发现算法进行多次选择的次数随着数据中元素的数量而减少。也就是说, 日志中的平均成本渐近接近1 .

elements    accesses    log-accesses
32          6.362279    1.272456
64          6.858437    1.143073
128         7.524225    1.074889
256         8.317139    1.039642
512         9.189112    1.021012
1024        10.112867   1.011287
2048        11.066819   1.006075
4096        12.038827   1.003236
8192        13.022343   1.001719
16384       14.013163   1.000940
32768       15.007320   1.000488
65536       16.004213   1.000263
131072      17.002441   1.000144
262144      18.001348   1.000075
524288      19.000775   1.000041
1048576     20.000428   1.000021

这是理想算法log2(n)的一个论点吗? 一般情况下 ?也许。最坏的情况当然不是这样。

另外,您不必一次选择log2(n)元素。您可以选择2并检查是否相等(但在退化的情况下,您将根本找不到复制),或者检查任何其他更大的数字以进行复制。在这一点上,所有选择元素和检查重复的算法都是相同的,只在它们选择的数量和识别重复的方式上有所不同。

如果您被告知要查找的元素是非唯一的元素,那么最快的方法肯定是沿数组迭代,直到找到两个相同的元素,然后返回该元素并停止查找。最多只能搜索一半数组。

我认为这是O(N),所以我想这真的没有帮助。

这似乎太简单了,所以我觉得我不能正确理解这个问题。

这里是 Don Johe's answer 红宝石:

#!/usr/bin/ruby1.8

def find_repeated_number(a)
  return nil unless a.size >= 3
  (0..a.size - 3).each do |i|
    [
      [0, 1],
      [0, 2],
      [1, 2],
    ].each do |j1, j2|
      return a[i + j1] if a[i + j1] == a[i + j2]
    end
  end
end

p find_repeated_number([1, 1, 2])   # => 1
p find_repeated_number([2, 3, 2])   # => 1
p find_repeated_number([4, 3, 3])   # => 1

o(n)

算法 RepeatedElement(a, n)

while (true) do
{
   i=Random() mod n+1; j=Random() mod n+1;
   // i and j are random numbers in the range [1,n]
   if ((i ≠ j) and a[i]=a[j])) then return;
}

类似 https://stackoverflow.com/a/1191881/199556 说明。

让我们比较3个元素(3个比较操作),在更糟的情况下,“相同”元素将出现一次。 因此,我们将尾部减少3,并将“相同”元素的计数减少1。

在最后一步(k次迭代之后),我们的尾部将包含(n/2)-k“相同”元素。让我们比较一下尾巴的长度。

一方面,它将是N-3K 另一方面(n/2)-k+1。最后一个未保存的元素可能存在。

N-3K=(N/2)-K+1

K=1/4*(n-2)

经过k次迭代,我们肯定会得到结果。

比较次数3/4*(n-2)

首先,现在已经过了我的睡觉时间,我应该知道,我不应该在公共场合发布代码而先尝试它,雅达,雅达。我希望我得到的批评至少是有教育意义的。-)

我相信这个问题可以重述为:“找出不止一次发生的数字。”

在绝对最坏的情况下,我们需要迭代列表的一半以上(1+n/2),然后才能找到非唯一数字的第二个实例。

最坏情况示例:数组[]=1、2、3、4、5、10、10、10、10、10

论 平均的 尽管如此,我们只需要迭代3或4个元素,因为一半的元素将包含非唯一的数字,即大致每隔一个数字。

完美均匀分布示例:

• 数组[]=1,10,2,10,3,10,4,10,5,10
• 数组[]=10,1,10,2,10,3,10,4,10,5

换言之,即使n=100万,您仍然只需要搜索;平均而言,在发现重复项之前的前3或4个元素。

固定/常量运行时的大O符号是什么,它不随n而增加?

代码:

int foundAt = -1;

for (int i=0; (i<N) && (foundAt==-1); i++)
{
    for (int j=i+1; j<N; j++)
    {
        if (array[i] == array[j])
        {
             foundAt = i;
             break;
        }
     }
}

int uniqueNumber = array[foundAt];

这是一个糟糕的面试问题。

1. 你自己也不知道答案。
2. 它背后没有任何商业案例,因此您很难向候选人解释它。

主要是因为第一个。你在找什么?候选人应该提出这个你不知道存在的O(log n)解决方案?如果你不得不问StackOverflow,你能合理地期望应聘者在面试中提出这个问题吗?

与上述答案相反,有一个解决方案 最坏情况 按要求的行为,o(log n) 运行时间 . 问题不在于用O(log n)比较最坏的情况(这是不可能的)找到解决方案,而是用O(log n)时间。

如果您可以并行地进行n次比较,那么解决方案就是一个微不足道的分而治之。 在现实世界中不太实际,但这是一个面试问题,而不是现实问题。

更新:我想你可以用O(N)处理器在固定时间内完成它。