算法--有序数组的不同绝对值个数

题目:

给定一个有序数组, 求它的元素的绝对值个数. 如数组[-3, -1, 0, 0, 2, 3, 5], 返回5.

分析:

第一种思路. 数组遍历一遍, 将每一个元素的绝对值放入一个Set里面, 最后求Set的大小. 这种方法虽然很简单, 但是空间复杂度不小, 为O(n). 那么能不能同样只遍历一遍, 空间复杂度为O(1)呢. 好吧, 下面来分析一下时间复杂度为O(n), 空间复杂度为O(1)的方法. 假设一下, 如果数组里面每一个元素的绝对值都不相同, 那么在遍历到第个元素的时候都令计数count加1, 那么最后的结果也是绝对值个数, 对吧? 如果有相邻两个相同的元素呢? 那么可以跳过这个元素不进行计数. 如果有正负两个元素绝对值相对呢? 那么这两个元素的和为0对吧, 然后令遍历的两个index, 小的加1, 大的减1, 同时count只计算一个数就可以了. 对吧?

接下来我们来看一下具体的Java代码吧:

 1 public int countDistinctAbs(int[] nums) {
 2     if (nums == null || nums.length == 0) {
 3         return -1;
 4     }
 5     int i, j, count;
 6     i = 0;
 7     j = nums.length - 1;
 8     count = 0;
 9     while(i < j) {
10         if (i < nums.length - 1 && nums[i] == nums[i+1]) {
11             continue;
12         }
13         if (j > 0 && nums[j] == nums[j-1]) {
14             continue;
15         }
16         if (nums[i]+nums[j] == 0){ //正负两个数的绝对值相同, 如果数组只存在正数或者负数, 则不存在这种情况, if分支会走到下面两种情况
17             i++;
18             j--;
19         } else if (nums[i] + nums[j] > 0) { // 说明正数的绝对值较大, 或者全是正数时, 只走该分支
20             j--;
21         } else if (nums[i] + nums[j] < 0) { // 说明负数的绝对值较大, 或者命题负数时, 只走该分支
22             i++;
23         }
24         count++
25     }
26     if (i == j) {
27         count++;
28     }
29     return count;
30 }

又解决了一道题目!!! 哈哈