校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 算法 > 字符串算法
题目

给一个有序数组,求每个数的平方的结果,不重复的有几个
-5,-5,-1,0,1,1,1,1,2,5
这里平方数不重复的一共4个,要求用在O(1)的空间复杂度下,用最优的时间复杂度实现

解答

绝对值相等可能有哪些情况呢?

两个同符号数的绝对值相等,这也意味着在有序数组中这个两个数是相邻的,这时只需要移动指针跳过相邻相等的数即可。
两个异符号数的绝对值相等,所以我们需要维护两个指针,一个指针从前往后移动,一个从后往前移。原因是前面的负数绝对值可能与后面整数的绝对值相等,我们需要比较前后两个指针绝对值的大小。
综上,我们需要维护两个指针,i开始指向数组第一个元素,i=0;j开始指向数组最后一个元素,j = nums.length-1。i,j指针的另外含义是:数组中索引小于i和大于j的元素都已经被处理了;i,j指向的是未处理元素中绝对值最大的两个元素。当i>j的时候表明所有的元素都已经被处理了,循环结束。


那么如何移动指针呢?

如果nums[i]与nums[j]的绝对值相等,此时执行i++,直到nums[i]的绝对值不等于nums[j]的绝对值(跳过相邻重复元素);j也是做类似的移动,只不过j是向前移,j--;最后计数器加1。
如果nums[i]的绝对值大于nums[j]的绝对值,我们移动指针i,并且计数器加1。原因?因为i和j指向未处理元素中绝对值最大的那个,nums[i]的绝对值已经是未处理元素中绝对值最大的两个数,也就是不可能存在一个未被处理的元素,它的绝对值与nums[i]的绝对值相等。所以这种情况下我们移动i指针。注意这里所说的移动指的是:执行i++直到nums[i]的绝对值发生了改变(跳过相邻相等的元素)。
如果nums[j]的绝对值大,那么与上面类似,移动j指针。

public int handle (int[] nums) {
       if(nums==null || nums.length==0)
             return 0;

       // result的缩写,最后的返回值
       int res = 0;
      //i是前指针;j是后指针
       int i = 0;

       int j = nums.length - 1;
      while (i <= j) {
             int num1=Math.abs(nums[i]);
             int num2=Math.abs(nums[j]);
             if (num1 > num2) {//移动i
                 // 这两个数的绝对值不相等
                 res += 1;
                 //过滤掉相邻的绝对值相等的数
                while(i<=j && Math.abs(nums[i])==num1)
                       i++;
             } else if (num1 < num2) {// 这两个数的绝对值不相等
                  res += 1;
                  while(i<=j && Math.abs(nums[j])==num2) //过滤掉相邻的绝对值相等的数
                         j--;
             } else {
                  res += 1;
                  while(i<=j && Math.abs(nums[i])==num1)//去重
                         i++;
                  while(i<=j && Math.abs(nums[j])==num2)//去重
                         j--;
             }
       }
       return res;
}


C 3条回复 评论
岸然

我想学习黑客,但是我没有文化

发表于 2024-06-28 21:00:00
0 0
下雨天睡觉

简直是我梦想中的offer,好想去上班

发表于 2022-10-29 23:00:00
0 0
童立

UI设计发展前景怎么样

发表于 2022-08-16 22:00:00
0 0