在包含正整数和负整数的向量中找到最小的缺失整数？

问题描述 投票：0回答：5

我正在编写一个操作来查找向量的最低缺失元素，V = 1..N + 1。这必须以 O(N) 时间复杂度执行。

解决方案一：

std::vector<int> A {3,4,1,4,6,7};

int main()
{
    int max_el = *std::max_element(A.begin(), A.end()); //Find max element
    std::vector<int> V(max_el);
    std::iota(V.begin(), V.end(), 1) //Populate V with all int's up to max element

    for(unsigned into i {0}; i < A.size(); i++)
    {
       int index = A[i] - 1;
       if(A[i] == V[index]) //Search V in O(1)
       {
         V[index] = max_el; //Set each to max_el, leaving the missing int 
       }
    }
    return *std::min_element(V.begin(), V.end()); //Find missing int as its the lowest (hasn't been set to max_el)
}

//Output: 2

这完全没问题。

但是，我现在正在尝试让它与包含负整数的向量一起使用。

解决方案二：

我的逻辑是采取相同的方法，但是根据向量的大小和向量中负整数的数量对索引进行“加权”：

std::vector<int> A {-1, -4, -2, 0, 3, 2, 1}
int main()
{
   int max_el = *std::max_element(A.begin(), A.end());
   int min_el = *std::min_element(A.begin(), A.end());
   int min_el_abs = abs(min_el); //Convert min element to absolute
   int total = min_el_abs + max_el;

   std::vector<int> V(total + 1);
   std::iota(V.begin(), V.end(), min_el);
   int index;

   //Find amount of negative int's
   int first_pos;
   for(unsigned int i {0}; i < A.size(); i++)
   {
      if(A[i] >= 0) {first_pos = i; break;}
   }

   for(unsigned int i {0}; i < A.size(); i++)
   {
      if(A[i] <= 0) //If negative
      {
          index = (A.size() - first_pos) - abs(A[i]);
       } else 
       {
          index = (A[i] + 1) + first_pos;
       }
       if(A[i] == V[index])
       {
          V[index] = 0;
       }
    } 
    return *std::min_element(V.begin(), V.end());
 } 

 //Output: -3

解决方案二无法比较两个向量（A 和 V）的值，因为使用上述方法使用 

positive
int 计算 index 不起作用。

1) 如何让我的解决方案 2 能够处理负整数的无序向量？

2）如何编辑我的解决方案 2 以处理正整数向量以及负整数向量？

c++ vector
5个回答
3
投票

你的第一个解决方案似乎是 O(max(N,M))，其中我认为 N 是向量 A 中的元素数量，M 是向量 V 的大小（或 max(Ai)），但是你正在循环多次通过两个向量（使用 

std::min_element
、
std::max_element
、
for
循环、V 和 
std::iota
的分配）。

此外，一旦纠正了几个拼写错误（缺少 

;
和 
into
而不是 
int
），您的程序就会返回从 
main()
找到的值，这有点奇怪。

您的第一个算法始终搜索范围 [1，A] 中的最大值，但它可以推广到查找范围 [min(Ai) 中的最低缺失元素， max(Ai)]，即使是负数。

我的方法与 L.Senioins 类似，但我使用了不同的库函数来尝试最小化循环数量。

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

template <class ForwardIt>
typename std::iterator_traits<ForwardIt>::value_type
lowest_missing(ForwardIt first, ForwardIt last)
{
    if ( first == last )
        throw std::string {"The range is empty"};
    // find both min and max element with one function
    auto result = std::minmax_element(first, last);

    // range is always > 0  
    auto range = *result.second - *result.first + 1;
    if ( range < 2 )
        throw std::string {"Min equals max, so there are no missing elements"};
    std::vector<bool> vb(range); // the initial value of all elements is false

    for (auto i = first; i != last; ++i)
        vb[*i - *result.first] = true;

    // search the first false
    auto pos = std::find(vb.cbegin(), vb.cend(), false);
    if ( pos == vb.cend() )  // all the elements are true
        throw std::string {"There are no missing elements"};

    return std::distance(vb.cbegin(), pos) + *result.first;
}

template <class ForwardIt>
void show_the_first_missing_element(ForwardIt first, ForwardIt last)
{
    try
    {
        std::cout << lowest_missing(first, last) << '\n';
    }
    catch(const std::string &msg)
    {
        std::cout << msg << '\n';
    }
}

int main() {
    std::vector<int> a { 1, 8, 9, 6, 2, 5, 3, 0 };
    show_the_first_missing_element(a.cbegin(), a.cend());

    std::vector<int> b { -1, -4, 8, 1, -3, -2, 10, 0 };
    show_the_first_missing_element(b.cbegin(), b.cend());
    show_the_first_missing_element(b.cbegin() + b.size() / 2, b.cend());

    std::vector<int> c { -2, -1, 0, 1, 2, 3 };
    show_the_first_missing_element(c.cbegin(), c.cend());

    std::vector<int> d { 3, 3, 3 };
    show_the_first_missing_element(d.cbegin(), d.cend());

    std::vector<int> e;
    show_the_first_missing_element(e.cbegin(), e.cend());

    return 0;
}

我的测试用例输出的结果是：

4
2
-1
没有缺失的元素
最小值等于最大值，因此不存在缺失元素
范围为空
2
投票

我的解决方案是创建一个 

bool
向量（或 
char
向量只是为了避免关于转换为 
bool
的编译警告），它具有所有可能元素的大小。所有元素都初始化为 0，然后分配为 1，表示该元素没有丢失。然后您需要做的就是找到第一个 0 元素的索引，它是最低的缺失元素。 

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

std::vector<int> A{ -1, 0, 11, 1, 10, -5 };

int main() {
    if (A.size() > 1) {
        int max_el = *std::max_element(A.begin(), A.end());
        int min_el = *std::min_element(A.begin(), A.end());
        int range = abs(max_el - min_el) + 1;

        std::vector<int> V(range, 0);

        for (size_t i = 0; i < A.size(); i++)
            V[A[i] - min_el] = 1;

        if (*std::min_element(V.begin(), V.end()) == 0)
            std::cout << std::distance(V.begin(), std::find(V.begin(), V.end(), 0)) + min_el;
        else
            std::cout << "There are no missing elements" << std::endl;
    }
    else
        std::cout << "There are no missing elements" << std::endl;

    std::cin.get();
}
1
投票

在花了一些时间思考之后，我将尝试给出我自己的问题的答案：

int main()
{
  std::vector<int> A {-3, -1, 0, 1, 3, 4};
  auto relative_pos = std::minmax_elment(A.begin(), A.end());
  std::vector<bool> Litmus( *(relative_pos.second) - *(relative_pos.first), false); //Create vector of size max val - min val)

  auto lowest_val = *(relative_pos.first);
  for(auto x : A)
  {
     Litmus[i - lowest_val] = true;
  }
  auto pos = std::find(Litmus.begin(), Litmus.end(), false); //Find the first occurring false value
  std::cout<< (pos - Litmus.begin()) + lower<<std::endl; //Print the val in A relative to false value in Litmus
}

该解适用于负数并且是线性的。

0
投票
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
int solution(vector<int> &A) {
    std::vector<int>::iterator it = std::max_element(A.begin(),A.end()); 
    try
    {
        sort(A.begin(),A.end());    
        std::vector<int>::iterator it = std::unique(A.begin(),A.end());
        A.resize(std::distance(A.begin(),it));

        for(int i = 0, j = 1; i < A.size(); i++)
        {
            if( A[i] != j)          
            {
                return j;
            }           
            j++;
        }

    }
    catch(exception &e)
    {
        std::cout<<e.what()<<std::endl;
    }
    return ++(*it);
}
0
投票
#include <algorithm>
#include <vector>

using namespace std;

const vector<int> DATA = {1, 3, 6, 4, 1, 2};

auto smallest_non_occuring = [](const vector<int>& A) -> int {
    const auto [min, max] = minmax_element(A.begin(), A.end());
    const auto range = *max - *min;
    vector visited(range, false);
    for (const auto& a : A) visited[a - *min] = true;
    auto pos_smallest = find(visited.begin(), visited.end(), false);
    return (pos_smallest - visited.begin()) + *min;
};

int main(){ return smallest_non_occuring(DATA); }
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.