在数组中查找元素,但元素可以跳转

Question

有一个数组,其中除了一个单元格之外的所有单元格都是0,我们想要找到该单个非零单元格的索引.问题是,每次检查此数组中的单元格时,该非零元素将执行以下操作之一:

1. 向前迈进1
2. 向后移动1
3. 留在原地.

例如,如果该元素当前位于第10位,并且我检查了什么arr[5],那么在我选中后该元素可能位于第9,10或11位arr[5].

我们只需要找到元素当前所处的位置,而不是它开始的位置(这是不可能的).

困难的部分是,如果我们写一个for循环,真的无法知道元素当前是在你面前还是在你身后.

如果有帮助,可以使用更多上下

1. 面试官确实给出了一个提示,也许我应该在检查x个细胞后将指针移回去.问题是,我什么时候应该搬回来,以及有多少个插槽？
2. 在"大声思考"的同时,我开始说一些常见的方法,希望有什么东西会受到影响.当我说递归时,面试官确实说"递归是一个好的开始".我不知道递归真的是正确的方法,因为我没有看到我如何能够同时进行递归和#1.
3. 采访者说这个问题在O(n ^ 2)中无法解决.所以我们至少看O(n ^ 3),甚至可能是指数.

Answer 1

Tl; dr:你最好的选择是依次检查阵列中的每个偶数索引,根据需要包裹多次,直到你找到你的目标.平均而言,你会在第二次传球中间偶然发现你的目标.

首先,正如许多人已经说过的那样,确实无法确保在任何给定的时间内找到目标元素.如果元素知道下一个样本的位置,它总是可以将其自身放置在其他地方.您可以做的最好的方法是以最小化预期访问次数的方式对数组进行采样 - 并且因为在每个样本之后您除了成功与否之外什么都不学习,并且成功意味着您停止采样,可以描述最佳策略只是作为一系列应该检查的索引,仅取决于您正在查看的数组的大小.我们可以通过自动化方式依次测试每个策略,看看它们的表现如何.结果将取决于问题的具体情况,所以让我们做一些假设:

• 问题没有指定我们目标的起始位置.让我们假设从整个阵列中均匀地选择起始位置.
• 问题没有说明目标移动的概率.为简单起见,我们可以说它独立于参数,例如数组中的当前位置,时间和样本历史.使用每个选项的概率1/3为我们提供最少的信息,所以让我们使用它.
• 让我们在100个 101元素的数组上测试我们的算法.另外,让我们测试每个算法一百万次,只是为了合理地确定它的平均案例行为.

我测试的算法是:

• 随机抽样:在每次尝试之后,我们忘记了我们在哪里,并随机选择一个全新的索引.每个样本都有独立的1/n成功机会,因此我们希望平均取样n个样本.这是我们的控制.
• 扫描:按顺序尝试每个位置,直到找到目标.如果我们的目标没有移动,平均需要n/2个样本.然而,我们的目标是移动,所以我们可能会在第一次扫描时错过它.
• 慢扫:同样的,除了我们在继续前几次测试每个位置.Patrick Trentin提出的减速因子为30倍,测试速度减缓2倍.
• 快速扫描:与慢速扫描相反.在第一个样本之后,我们跳过(k-1)个单元格,然后再测试下一个单元格.第一遍从ary [0]开始,下一遍在ary [1],依此类推.每个加速因子(k)从2到5进行测试.
• 左右扫描:首先我们从左到右依次检查每个索引,然后从右到左依次检查每个索引.如果它始终在移动(不是这样),那么该算法将保证找到我们的目标.
• 聪明贪心:Aziuth提出.这个算法背后的想法是我们跟踪每个单元保持目标的概率,然后总是以最高的概率对单元进行采样.一方面,这种算法相对复杂,另一方面它听起来应该给我们最优的结果.

结果:

结果显示为[平均]±[标准推导].

• 随机抽样:100.889145±100.318212

  此时我在代码中意识到了fencepost错误.我们有一个控制样本的好东西.这也确定了我们在两个或三个有用精度数字(sqrt #samples)的球场中,这与此类型的其他测试一致.

• 扫描:100.327030±91.210692

  我们的目标挤压净井的可能性抵消了目标平均花费n/2时间达到净值的效果.该算法的平均效果并不比随机样本好,但它的性能更加一致,并且实现起来并不困难.

• 慢扫(x0.5):128.272588±99.003681

  虽然我们网的缓慢移动意味着我们的目标可能会在第一次扫描期间陷入网中并且不需要第二次扫描,但这也意味着第一次扫描需要两倍的时间.总而言之,依靠目标移动到我们身上似乎效率低下.

• 快速扫描x2:75.981733±72.620600

• 快速扫描x3:84.576265±83.117648
• 快速扫描x4:88.811068±87.676049

• 快速扫描x5:91.264716±90.337139

  那......起初有点令人惊讶.虽然跳过其他所有步骤意味着我们完成每圈的两次转弯,但每圈也实际上遇到目标的几率降低.一个更好的视图是在扫帚空间中比较Sweep和FastSweep:旋转每个样本,使得被采样的索引始终为0,目标向左漂移一点.在Sweep中,目标每步以0,1或2的速度移动.与斐波那契基地快速平行告诉我们,目标应该在62%的时间内击中扫帚/网.如果它未命中,则需要再转100圈.在FastSweep中,目标每步移动速度为1,2或3,这意味着它会更频繁地错过,但它也需要一半的时间来重试.由于重试时间下降超过命中率,因此使用FastSweep over Sweep是有利的.

• 左右扫描:100.572156±91.503060

  大部分行为都像普通的扫描,其分数和标准推导反映了这一点.结果并不太令人惊讶.

• Aziuth的聪明贪心:87.982552±85.649941

  在这一点上,我不得不承认我的代码中有一个错误:这个算法严重依赖于它的初始行为(Aziuth没有指定,并且在我的测试中被选择随机化).但是性能问题意味着该算法每次都会选择相同的随机顺序.结果然后是随机化的特征而不是整个算法的特征.

  总是挑选最可能的地点应该尽快找到我们的目标,对吧？不幸的是,这种复杂的算法几乎与Sweep 3x竞争.为什么？我意识到这只是推测,但让我们看看Smart Greedy实际生成的序列:在第一次传递期间,每个单元格包含目标的概率相等,因此算法必须选择.如果它随机选择,它可能会在20%的细胞中占据,然后才有可能达到所有细胞.之后,在最近没有对阵列进行采样的情况下,景观基本上是平滑的,因此算法最终会停止扫描并开始随机跳转.真正的问题是算法过于贪婪,并不真正关心放牧目标,因此它可以更容易地选择目标.

  然而,这种复杂的算法确实比简单的扫描和随机采样器都要好.然而,它仍然不能与FastSweep的简单性和惊人的效率竞争.重复测试表明,初始随机化可以将效率提高到80%运行时间(20%加速)和90%运行时间(10%加速)之间.

最后,这是用于生成结果的代码:

class WalkSim
  attr_reader :limit, :current, :time, :p_stay
  def initialize limit, p_stay
    @p_stay = p_stay
    @limit = limit
    @current = rand (limit + 1)
    @time = 0
  end

  def poke n
    r = n == @current
    @current += (rand(2) == 1 ? 1 : -1) if rand > @p_stay
    @current = [0, @current, @limit].sort[1]
    @time += 1
    r
  end

  def WalkSim.bench limit, p_stay, runs
    histogram = Hash.new{0}
    runs.times do
      sim = WalkSim.new limit, p_stay
      gen = yield
      nil until sim.poke gen.next
      histogram[sim.time] += 1
    end
    histogram.to_a.sort
  end
end

class Array; def sum; reduce 0, :+; end; end

def stats histogram
  count = histogram.map{|k,v|v}.sum.to_f
  avg = histogram.map{|k,v|k*v}.sum / count
  variance = histogram.map{|k,v|(k-avg)**2*v}.sum / (count - 1)
  {avg: avg, stddev: variance ** 0.5}
end

RUNS = 1_000_000
PSTAY = 1.0/3
LIMIT = 100

puts "random sampling"
p stats WalkSim.bench(LIMIT, PSTAY, RUNS) { 
  Enumerator.new {|y|loop{y.yield rand (LIMIT + 1)}}
}

puts "sweep"
p stats WalkSim.bench(LIMIT, PSTAY, RUNS) { 
  Enumerator.new {|y|loop{0.upto(LIMIT){|i|y.yield i}}}
}

puts "x0.5 speed sweep"
p stats WalkSim.bench(LIMIT, PSTAY, RUNS) { 
  Enumerator.new {|y|loop{0.upto(LIMIT){|i|2.times{y.yield i}}}}
}
(2..5).each do |speed|
  puts "x#{speed} speed sweep"
  p stats WalkSim.bench(LIMIT, PSTAY, RUNS) { 
    Enumerator.new {|y|loop{speed.times{|off|off.step(LIMIT, speed){|i|y.yield i}}}}
  }
end
puts "sweep LR"
p stats WalkSim.bench(LIMIT, PSTAY, RUNS) { 
  Enumerator.new {|y|loop{
    0.upto(LIMIT){|i|y.yield i}
    LIMIT.downto(0){|i|y.yield i}
  }}
}

$sg_gen = Enumerator.new do |y|
  probs = Array.new(LIMIT + 1){1.0 / (LIMIT + 1)}
  loop do
    ix = probs.each_with_index.map{|v,i|[v,rand,i]}.max.last
    probs[ix] = 0
    probs = [probs[0] * (1 + PSTAY)/2 + probs[1] * (1 - PSTAY)/2,
             *probs.each_cons(3).map{|a, b, c| (a + c) / 2 * (1 - PSTAY) + b * PSTAY},
             probs[-1] * (1 + PSTAY)/2 + probs[-2] * (1 - PSTAY)/2]

    y.yield ix
  end
end

$sg_cache = []
def sg_enum; Enumerator.new{|y| $sg_cache.each{|n| y.yield n}; $sg_gen.each{|n| $sg_cache.push n; y.yield n}}; end

puts "smart greedy"
p stats WalkSim.bench(LIMIT, PSTAY, RUNS) {sg_enum}

Answer 2

不要忘记有关循环的一切。将此数组复制到另一个数组，然后检查哪些单元格现在非零。例如，如果您的主数组是 mainArray[] 您可以使用：

int temp[sizeOfMainArray]
int counter = 0;
while(counter < sizeOfArray)
{
    temp[counter] == mainArray[counter];
}
//then check what is non-zero in copied array
counter = 0;

while(counter < sizeOfArray)
{
    if(temp[counter] != 0)
{
    std::cout<<"I Found It!!!";
}
}//end of while