当前位置:  开发笔记 > 编程语言 > 正文

在包含正和负int的向量中找到最低缺失整数?

如何解决《在包含正和负int的向量中找到最低缺失整数?》经验,为你挑选了0个好方法。

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

解决方案一:

std::vector A {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::vector 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 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的向量和向量的向量?

推荐阅读
重庆制造漫画社
这个屌丝很懒,什么也没留下!
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有