按0和1的顺序查找1的数字

Question

这是一个面试问题.最初我发现它非常容易和愚蠢.最后我没能解决这个问题.:(

问题是,我们有一个数组,其序列为0,后跟1的序列和0的序列.这样的事情.

   int [] arr ={0,0,0,1,1,1,0,0,0}

现在,在log(n)时间内找到数组中的1的数量.

任何的想法 ？:(

Answer 1

好吧,怎么把这个......

你不能.您目前对阵列只有三个假设:

• 它不是以a开头的1,
• 它不会以a结束1,
• 对于任何两个人来说1,0他们之间没有.

为了在数组中查找内容,您可以使用线性搜索和二进制^*搜索.线性搜索似乎不合适,因为您希望实现对数时间.但是,对于二进制搜索,您需要arr[i] <= arr[j]所有这些i < j.由于情况并非如此,你不知道哪一半包含了1.这意味着您需要检查两侧,这会导致线性复杂性.

为什么n-ary(n> = 2)搜索不起作用

那么为什么没有任何二进制搜索工作呢？在回答这个问题之前,让我们快速介绍二进制搜索实际上是如何工作的,因为似乎有点混乱:

二进制搜索如何工作？

二进制搜索工作得很好,因为它可以大大减少问题的大小:在每次迭代中,问题大小减半.

例如,假设我们正在5按顺序查找000011223334456.

这很有效,因为我们得到以下顺序:我们首先检查中间,即2.因此我们知道解决方案在右侧,我们永远不必检查左侧.右侧中间是四个,所以我们可以再次切断左半边.下一个中间是5.我们停止:

在图像中,永远不会检查红色部分.从不.对于复杂性,让ñ是我们最初的问题大小.一步之后,我们的问题就是大小n/2.在第k步之后,它具有大小n /(2 ^ k).因此,如果k = log ₂(n),我们将问题减少到第一个.由于我们在每一步中只检查了一个值,并且我们总共有log ₂(n)步(向上舍入到下一个积分),因此我们具有对数时间复杂度.

为什么二进制搜索在您的情况下不起作用

简短的回答是:因为您的问题没有排序.让我们尝试使用二进制搜索:

一步后会发生什么？

检查中间值并不能给我们任何信息,除非我们知道它不是1.我们不知道是否需要遍历左侧或右侧树.因此,我们需要遍历两个人.为了创建确定性算法,我们需要修复所有应用程序的遍历顺序.如果我们从右到左遍历,我们发现它相对较快:

但如果1在左边,我们会检查几乎所有元素.您还注意到我们不能排除真实二进制搜索中的节点数量.

顺便说一下,交替变体也存在同样的问题,因为交替仅意味着基于水平的遍历.您可以根据节点检查节点,而不是跟踪路径:

一些评论建议在两棵树中并行/同时搜索.虽然这实际上减少了总时间,但是在图灵机的意义上测量时间复杂度.在某个时刻,你将耗尽条带或CPU.请记住,这是关于理论计算时间复杂度的.

为什么找到一个1这么重要？

如果在对数时间内找不到单个值,则在对数时间内找不到一对值,例如(0,1).但是如果你知道单个1的位置,那么左侧和右侧都是有序集合,因为它们是000....011..11并且11....1100...00可以使用二进制搜索.

那么实际上可以在对数时间内解决它吗？

在所有讨论之后,应该清楚我们需要线性运行时来查找单个1.

然而,与假设一起,我们可以在对数时间内找到边缘并减去它们的位置:

• 数组有一个1at位置k(你的例子建议在一个位置size/2)

如果您想知道这有何帮助,请查看上一节.

但是,如果没有额外的假设,就无法做到.

^{*或任何其他n-ary搜索(n> 2),但它们都具有对数成本}