我正在编写一个操作来找到矢量的最低缺失元素,V = 1..N + 1.这必须以O(N)时间复杂度执行.
解决方案一:
std::vectorA {3,4,1,4,6,7}; int main() { int max_el = *std::max_element(A.begin(), A.end()); //Find max element std::vector 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
这完全没问题.
但是,我现在正试图使用包含负int的向量.
解决方案二:
我的逻辑是采用相同的方法,但是根据向量的大小和向量中的负int的数量来"权衡"索引:
std::vectorA {-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 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
解决方案2无法比较两个向量(A和V)的值,因为index
使用上述方法计算带有正 int的值不起作用.
1)如何使我的解决方案2使用负int的无序向量?
2)如何编辑我的解决方案2以使用带有负int的向量和向量的向量?