首页 > 代码库 > 有序数组每个数平方后，不同数字的个数？O(n)
有序数组每个数平方后，不同数字的个数？O(n)
此乃一道笔试题，当时的确也出来啦。(但是在细节上还是出错啦，对多次重复出现的数字可能会重复计数，没有记录上次删除的元素)
如题，有序数组，可以知道平方之后在两边的数据较大，中间的数据较小。
因此可以使用两个下标，从两边向中间扫描。将绝对值大的数字删掉，计数即可，并记录刚才删除的数值的绝对值，以免出现多次相同的数据，重复计数的问题。
具体看完整代码：
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; ///数字为 115 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 }
有序数组每个数平方后，不同数字的个数？O(n)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。