c++ - 如何不断从 vector 中移除奇数位置的值，直到我们只剩下一个？

Question

令 J 为具有值 (0, 1, 1, 2, 3, 5, 8, 3, 1) 的 vector

我想继续从 vector 中移除奇数位置的所有值，直到 J 中只剩下一个元素。

(0, 1, 1, 2, 3, 5, 8, 3, 1) => (1, 2, 5, 3) => (2,3) => (3)

我如何实现这一目标？

我的方法:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  int J[] = {0, 1, 1, 2, 3, 5, 8, 3, 1};
  int len=sizeof(J)/sizeof(J[0]);
  vector<int> Jvec;
  for (int i=0; i<len; i++) {  //Putting the values of array into Jvec
    Jvec.push_back(J[i]);
  }

  while (Jvec.size()!=1) {
    vector<int> oddJ;
    for (int k=0; k<Jvec.size(); k=k+2) {  //Storing values of odd places
      oddJ.push_back(Jvec[k]);
    }

    for (int i=0; i<oddJ.size(); i++) {
      Jvec.erase(remove(Jvec.begin(), Jvec.end(), oddJ[i]), Jvec.end()); //removing values from vector by value, not index
    }
  }
  cout << Jvec[0];
  return 0;
}

我得到 5 个而不是 3 个。我的逻辑有问题吗？我哪里错了？

Answer 1

实际上，对于您的问题，有一个非常简洁快速的解决方案。

因为你想删除每一步的第 1、3、5 等索引，数组是0-based，你实际上应该删除第 0、2、4 索引每一步。

以下是一些有助于搜索答案的观察结果:

• 在每一步中，数组都会减半，这意味着在 O(logN) 步中您将得到一个大小为 1 的数组。

• 在最后一步，搜索值的索引为 0。

• 在每一步(但最后一步)中，搜索到的值都有一个奇数索引，因此它会被保留，直到数组大小达到 1。

因此，在最后一步中，搜索值的索引为 0，在上一步中，它的索引为 1，在之前的步骤中，它的索引为 3 依此类推。

我们可以清楚地看到，从0开始，索引翻倍后加上1，这样就变成了奇数，并没有被删除。这种情况正好发生 log n 次。

因此，为了跟踪我们最终应该打印的数字的索引，我们可以这样做:

int[] values = {0, 1, 1, 2, 3, 5, 8, 3, 1};
int n = values.length, index = 0;
while (n > 1) {
  index = 2 * index + 1;
  n /= 2;
}
System.out.println(values[index]);

我用 Java 编写了代码，但您可以轻松地将其改编为您选择的语言。

这给出了 O(logN) 的总体复杂度，其中 N 是 values 数组的大小。