c++ - 如何继续从向量中删除奇数位置的值，直到我们只剩下一个？

问题描述

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

我想继续从向量中删除奇数位置的所有值，直到 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。我的逻辑有问题吗？我哪里错了？

标签： c++arraysalgorithmvectorlambda

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

由于您想在每个步骤中删除第 1、第 3、第 5 等索引，因此数组是基于 0 的，您实际上应该在每个步骤中删除第 0、第 2、第 4 个索引。

以下是一些观察结果，在搜索答案时会有所帮助：

在每一步中，数组都会减半，这意味着在O(logN)步骤中您将获得一个 size 的数组1。
在最后一步，搜索到的值具有 index 0。
在每一步（但最后一步）上，搜索到的值都有一个奇数索引，因此它会被保留，直到数组大小变为1.

因此，在最后一步，搜索值的索引是0，在上一步它有 index 1，在前一步它有 index3等等。

我们可以清楚地看到，从开始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数组的大小。

c++ - 如何继续从向量中删除奇数位置的值，直到我们只剩下一个？

问题描述

解决方案

推荐阅读