有序数组的不同绝对值个数

题目

给定一个有序数组，求它的元素不同的绝对值个数。

比如

[-3, -1, 0, 0, 1, 1, 2, 5]

返回

5

分析

第一种方法

首先一个循环将数组所有的负数转换为正数，然后对整个数组进行排序。

但循环一遍的时间复杂度为 O(n)，排序如果用堆排序，平均时间复杂度为 O(nlogn)，空间复杂度为 O(1)。因此整体的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。而既然题目已经保证了有序数组，那有没有更快的方法呢？

第二种方法

我们可以用两个索引，索引 i 和 索引 j 分别从数组两端向中间移动，如果当前元素和下一个元素相等则跳过，如果右边的绝对值大于左边的绝对值，则索引 j 左移，如果左边的绝对值大于右边的绝对值，则索引 i 右移，如果两边绝对值相等，则索引同时左移和右移，每次移动计数加一。直到索引相遇时结束，如果相遇后索引刚好相等，则计数最后再加一。

这样时间复杂度就为 O(n)，空间复杂度为 O(1)。

实现

使用 Golang 实现的源码如下：

func getDistinctAbsCount(nums []int) int {
    i := 0
    j := len(nums) - 1
    count := 0
    for i < j {
        if i < len(nums)-1 && nums[i] == nums[i+1] {
            // skip duplicated
            i += 1
            continue
        }
        if j > 0 && nums[j] == nums[j-1] {
            // skip duplicated
            j -= 1
            continue
        }

        sum := nums[i] + nums[j]

        if sum > 0 {
            // abs(nums[i]) < abs(nums[j])
            j -= 1
        } else if sum < 0 {
            // abs(nums[i]) > abs(nums[j])
            i += 1
        } else {
            // abs(nums[i]) == abs(nums[j])
            i += 1
            j -= 1
        }
        count += 1
    }
    if i == j {
        count += 1
    }
    return count
}

可在这里在线运行：https://play.golang.org/p/lmOI5ZNkMNf