c++ - 查找具有真值 C++ 的下一个数组索引

Question

我有一个像这样的 bool 数组:

bool arr[] = { false, true, false, false, false, true };

我实现了一个算法来找到下一个 true值取决于当前索引:

bool isNewRound = false;

int get_next_true(int index) {
    for(int i=index + 1; i<arr.size(); i++) {
        if (arr[i]) {
            return arr[i];
        }
    }
    
    isNewRound = true;

    for(int i=0; i<index; i++) {
        if (arr[i]) {
            return arr[i];
        }
    }

    return index;
}

我不喜欢我的解决方案，因为它使用两个循环而不是一个循环。我正在考虑使用 while循环，但在这种情况下，它需要一个内部计数器。
如果可能的话，我需要对当前的解决方案进行一些优化，也许还需要一些关于如何改进我的方法的建议。
附言如果我能检测到我已经到达数组的末尾，那就太好了。
谢谢

Answer 1

你的方法的时间复杂度是 O(n)

查询时间复杂度 O(1) 解决方案

const int n = 6;
bool arr[n] = { false, true, false, false, false, true };
int next_index[n];

int get_next_true(int index) {
  return next_index[index];
}

int main() {
  int true_index = -1;
  for (int i = n - 1; i >= 0; i--) {
    next_index[i] = true_index;
    if (arr[i] == true)
      true_index = i;
  }
  for (int i = n - 1; i >= 0; i--) {
    if (next_index[i] == -1)
      next_index[i] = true_index;
    else
      break;
  }
  printf("%d\n", get_next_true(2));
}

查询时间复杂度 O(log2n) 解决方案

您可以维护 arr的前缀和(将 true 视为值 1)然后使用二分查找找到下一个真值的索引。

一个简单的演示:

const int n = 6;
bool arr[n] = { false, true, false, false, false, true };
int prefix[n];
bool isNewRound = false;

int get_next_true(int index) {
  int pos = std::upper_bound(prefix + index + 1, prefix + n, prefix[index]) - prefix;
  if (pos != n)
    return pos;
  isNewRound = true;

  pos = std::upper_bound(prefix, prefix + index + 1, 0) - prefix;
  if (arr[pos] == false)
    return -1; // Not Found

  return pos;
}

另外，记得在调用 get_next_true 之前做一些预处理:

prefix[0] = arr[0];
for (int i = 1; i < n; i++) {
  prefix[i] = arr[i] + prefix[i - 1];
}

查询和修改时间复杂度为 O(log2n) 的元素

请注意，如果 arr不是固定数组(你可能想修改它)，你需要使用一些数据结构，比如 segment tree .