我正在编写一个操作来查找 vector 中缺失最少的元素 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
这完全没问题。
但是,我现在正试图让它与包含负整数的 vector 一起工作。
方案二:
我的逻辑是采用相同的方法,但是根据 vector 的大小和 vector 中负整数的数量“加权”索引:
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
解决方案二无法比较两个 vector (A 和 V)的值,因为使用上述方法和 positive 计算 index
不起作用.
1) 如何让我的解决方案 2 与负整数的无序 vector 一起工作?
2) 如何编辑我的解决方案 2 以处理正 vector 和负整数 vector ?
最佳答案
您的第一个解决方案似乎是 O(max(N,M)),其中我认为 N 是 vector A 中的元素数,M 是 vector V 的大小(或 max(Ai)),但是您要多次循环遍历这两个 vector (使用 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 There are no missing elements Min equals max, so there are no missing elements The range is empty
关于c++ - 在包含正整数和负整数的 vector 中找到最小的缺失整数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41593549/