2465. 不同的平均值数目

这道题挺容易的。主要是排序+哈希。题目里有明显的去重的意思,所以哈希set是肯定有的。找最大最小,最方便的就是排序。这里我为了操作方便,把数组nums拷贝到了集合list里面。排一次序,之后取最大值最小值都很方便。

Collections.sort()方法,可以给Collection集合排序。

我的答案是这样:

class Solution {
    Set<Double> set = new HashSet<Double>();

    public int distinctAverages(int[] nums) {
        int nlen = nums.length;
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < nlen; i++) {
            list.add(nums[i]);
        }

        int max;
        int min;
        double avg;
        Collections.sort(list);

        while(list.size() > 0) {
            max = list.get(list.size() - 1);
            min = list.get(0);

            list.remove(list.size()-1);
            list.remove(0);
            avg = (max+min)*1.0/2;

            set.add(avg);

        }

        return set.size();
    }
}

看了题解,发现自己的思路还有很大的优化空间。题解结合了双指针,以及所谓的删除也没必要真的删去,用双指针维护一段有效区间即可。avg也没必要切切实实求出来,因为题干要求的是求不同平均值的数目,数目从set的长度就可以体现。因此,如果两数的和相同平均值就会相同,没必要把平均值的具体答案求出。

这样算法的效率大大提升。

class Solution {
    public int distinctAverages(int[] nums) {
        Arrays.sort(nums);
        Set<Integer> seen = new HashSet<Integer>();
        for (int i = 0, j = nums.length - 1; i < j; ++i, --j) {
            seen.add(nums[i] + nums[j]);
        }
        return seen.size();
    }
}
06-04 14:16