X

LEETCODE 1207. Unique Number of Occurrences 解题思路分析

题目大意:

独一无二的出现次数

给你一个整数数组 arr,请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的,就返回 true;否则返回 false

示例 1:

输入:arr = [1,2,2,1,1,3]
输出:true
解释:在该数组中,1 出现了 3 次,2 出现了 2 次,3 只出现了 1 次。没有两个数的出现次数相同。 

示例 2:

输入:arr = [1,2]
输出:false

示例 3:

输入:arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出:true

提示:

  • 1 <= arr.length <= 1000
  • -1000 <= arr[i] <= 1000

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1207

解题思路分析:

这道题的难度不大,只要统计出每种数字出现的次数后,查看是否存在相同次数即可。

完整代码:

public boolean uniqueOccurrences(int[] arr) {
    // 排序数组,使相同的数字能连续显示
    Arrays.sort(arr);
    // 定义memo数组,memo[i]表示是否存在出现次数为i次的数字
    boolean[] memo = new boolean[arr.length+1];
    // 初始化前一个数字为数组首元素。
    // 当前数字出现次数为1
    int preNum = arr[0], count=1;
    for(int i=1;i<arr.length;i++){ // 从数组第二个数字开始循环
        if(arr[i]==preNum){ // 当前数字等于前数字
            count++; // 出现次数加一
        }else{ // 当前数字不同于前数字
            if(memo[count]){ // 如果前数字出现次数已经存在
                return false; // 返回false
            }
            memo[count]=true; // 将前数字出现次数记为true
            preNum = arr[i]; // 更新前数字为当前数字
            count=1; // 当前数字出现次数还原为1
        }
    }
    return !memo[count];
}

本题解法运行时间为1ms。

Runtime: 1 ms, faster than 99.67% of Java online submissions for Unique Number of Occurrences.

Memory Usage: 34.6 MB, less than 100.00% of Java online submissions for Unique Number of Occurrences.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1207-unique-number-of-occurrences-解题思路分析/
Categories: leetcode
kwantong: