c++ - 查找不在索引向量中的索引

Question

如何查找不在数组索引中的索引？例如。如果索引向量是(2, 8, 6, 9). 那么结果应该是(1,3,4,5,7)。R 具有(not) %in%执行此操作的功能。一种天真的方法是创建一个标志数组。但是在非索引上创建标志和迭代将是两个不同的循环。有没有办法在一个循环中做到这一点？

Answer 1

这应该有效：

int j = 0;
for(int i = 0;; ++i) {
  if(oldvec[j] == i) {
    j++;
    if(j >= oldvec.length())
      break;
  } else {
    newvec.push_back[i];
  }
}

新答案：

  std::set<int> result;
  int max = -1;
  for(unsigned int i=0; i<oldvec.size(); ++i)
  {
    int cur = oldvec[i];
    while(max < cur) {
      max++;
      result.insert(max);
    }
    result.erase(cur);
  }

那个怎么样？:) 等等，结果必须是 std::vector 吗？

Answer 2

先排序，然后检查“宇宙”中first的last数字。检查此功能。根据您的示例，输入将是A = [2, 8, 6, 9], first = 1, last = 9。你得到解决方案out。请注意，该函数会对其进行修改A以对其进行排序。

void getComplement(std::vector<unsigned int> &A, 
  size_t first, size_t last, std::vector<unsigned int> &out)
{
  out.clear();
  if(last < first) return;

  const size_t T = last - first + 1;
  if((int)T - (int)A.size() > 0) out.reserve(T - A.size());

  if(A.empty())
  {
    for(size_t k = first; k <= last; ++k) out.push_back(k);
  }
  else
  {
    std::sort(A.begin(), A.end());

    std::vector<unsigned int>::const_iterator ait = A.begin();

    // elements before the first element of A
    for(size_t k = first; k < *ait; ++k) out.push_back(k);

    // middle elements
    std::vector<unsigned int>::const_iterator bit = ait + 1;
    for(; bit != A.end() ; ++ait, ++bit)
    {
      for(size_t k = *ait + 1; k < *bit; ++k) out.push_back(k);
    }

    // elements after the last element of A
    for(size_t k = A.back() + 1; k <= last; ++k) out.push_back(k);
  }

}

Answer 3

不排序：

#include <iostream>
#include <vector>

struct NaturalNumber {
    unsigned value;
    bool valid;

    NaturalNumber(unsigned value = 0)
    :   value(value), valid(true)
    {}
};

typedef std::vector<NaturalNumber> NaturalNumbers;

NaturalNumbers natural_number_range(unsigned n) {
    NaturalNumbers result;
    result.resize(n);
    for(unsigned i = 0; i < n; ++i) result[i] = i;
    return result;
}

int main(int argc, char* argv[]) {
    NaturalNumbers n0 = { 2, 8, 6, 9 };
    NaturalNumbers n1 = natural_number_range(10);
    for(NaturalNumbers::const_iterator pos = n0.begin(); pos != n0.end(); ++pos) {
        n1[pos->value].valid = false;
    }
    for(NaturalNumbers::const_iterator pos = n1.begin(); pos != n1.end(); ++pos) {
        if(pos->valid)
            std::cout << pos->value << std::endl;
    }
    return 0;
}

它只是将排序委托给一个标志，以存储无效数据为代价。也没有单循环！