未排序的二进制数组中第一次出现 1

Question

我正在解决在未排序的 1 和 0 数组中找到第一个 1 的问题。如果找到任何 1，程序应该 return 索引，否则 return -1。我想对这个问题有分而治之的解决方案，但我正在为基本情况而苦苦挣扎。

def first_one(A):
  n = len(A)
  leftmost = 0
  if n <= 1:
  # probably would be when n <=1 ? I was returning 0 if A[0] == 1 or n otherwise
  # but this lead to the final result always being determined by the first index. 
    
  idx_left = first_one(A[:int(n/2)])
  idx_right = first_one(A[int(n/2):])
  result = min(idx_left, idx_right)
  if result == n:
    return -1
  else:
    return result

那么我的基本情况应该是什么——始终检索实际的第一个索引而不是 0（或 -1）？我想不出任何其他基本情况。

Answer 1

您遇到的问题是您不记得后续调用中数组的开头。要缓解此问题，您必须在原始数组中保留有关当前位置的信息。我要么将数组的起始索引添加到调用结果中，要么在每次调用时只传递子数组的“位置”。

您在问题末尾提出的基本情况应该没问题；) 由于并行处理，嵌套时间请明确说明您想要 'divide and conquer' 解决方案。它将阻止提出更简单的顺序解决方案。

使用分而治之的示例解决方案：

def first_one(A):
  if len(A) == 0:
    return -1

  return first_one_subarray(A, 0, len(A) - 1)

def first_one_subarray(A, start, end):
  # Incorrect subarray
  if start > end or start > len(A) - 1:
    return -1

  # Check if 1 is on 'first' position
  if A[start] == 1:
    return start
    
  # Divide into two parts
  split_point = max(start + 1, round(end / 2))
  result_left = first_one_subarray(A, start + 1, split_point)
  result_right = first_one_subarray(A, split_point + 1, end)
  
  if result_left != -1:
    return result_left
  else:
    return result_right

未排序的二进制数组中第一次出现 1

First occurrence of 1 in unsorted binary array

python

algorithm

search