有序数组每个数平方后,不同数字的个数?O(n)分析

访客 阅读:140 2020-10-19 15:34:54 评论:0

此乃一道笔试题,当时的确也做出来啦。(但是在细节上还是出错啦,对多次重复出现的数字可能会重复计数,没有记录上次删除的元素)

 

如题,有序数组,可以知道平方之后在两边的数据较大,中间的数据较小。

          

因此可以使用两个下标,从两边向中间扫描。将绝对值大的数字删掉,计数即可,并记录刚才删除的数值的绝对值,以免出现多次相同的数据,重复计数的问题。

具体看完整代码:

 1 #include <iostream> 
 2 #include <vector> 
 3 #include <algorithm> 
 4 using namespace std; 
 5  
 6 int squareUniqueNum(vector<int> &ver){ 
 7     int len = ver.size(); 
 8     if(len < 2) 
 9         return len; 
10  
11     int i = 0; 
12     int j = len - 1; 
13     int pre = abs(ver[0]);  ///记录上次删除数据的绝对值 
14     int num = 1;    ///数字为 1 
15     while(i<=j){ 
16         ///每次删除绝对值较大的数字,并记录下删除是数字的绝对值,绝对值相同的只计数一次 
17         if(abs(ver[i]) > abs(ver[j])){ 
18             if(pre != abs(ver[i])){ ///如果没有删过 
19                 num++; 
20                 pre = abs(ver[i]); 
21             } 
22             i++; 
23         } 
24         else{ 
25             if(pre != abs(ver[j])){ ///如果没有删过 
26                 num++; 
27                 pre = abs(ver[j]); 
28             } 
29             j--; 
30         } 
31     } 
32     return num; 
33 } 
34  
35 int main() 
36 { 
37     vector<int> ver({-5,-3,-1,1,1,2}); 
38     int num = squareUniqueNum(ver);    ///求有序数组中数字平方后,消重结果中数字的个数 
39     cout<<num<<endl; 
40     return 0; 
41 }

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
关注我们

扫一扫关注我们,了解最新精彩内容