有序数组每个数平方后，不同数字的个数O(n)

wyy 2020年10月19日程序员 398 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 }