算法-数组-独一无二的出现次数

系统管理员 2022-11-20 09:36 111阅读 0赞

# 算法-数组-独一无二的出现次数 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/unique-number-of-occurrences/

## 1.2 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70_pic_center]

# 2 数组 #

## 2.1 思路 ##

用数组分别记录

*  每个独立数字对应出现次数
 *  独立的数字有哪些
 *  独立数字对应出现次数是否唯一

虽然比较绕，但数组是最快的，比什么HashMap都快得多，因为没有其他开销，直接拿下标O(1)就能取出数字，没有冲突。

## 2.2 代码 ##

class Solution { 
        public boolean uniqueOccurrences(int[] arr) { 
            // 每个数字对应出现的次数
            int[] count = new int[2001];
            // 独立的数字
            int[] distinct = new int[arr.length];
            // 独立数字总数记录
            int d = 0;
            // 独立数字出现的次数是否出现
            boolean[] exist = new boolean[1000];
            
            for(int i = 0; i < arr.length; i++){ 
                // 替换为[0, 2000]的数字
                int replace = arr[i] + 1000;
                if(count[replace] == 0){ 
                    // 该数字未出现过
                    count[replace] = 1;
                    distinct[d++] = replace;
                } else{ 
                    // 该数字已经出现过
                    count[replace]++;
                }
            }
            for(int i = 0; i < d; i++){ 
                // 检查独立数字出现次数是否唯一
                if(exist[count[distinct[i]]] == false){ 
                    // 该数字出现次数目前唯一
                    exist[count[distinct[i]]] = true;
                }else{ 
                    // 该数字出现次数不唯一
                    return false;
                }
            }
            return true;
        }
    }

## 2.3 时间复杂度 ##

O(N)  
![在这里插入图片描述][20201028102358318.png_pic_center]

## 2.4 空间复杂度 ##

O©

# 3 HashMap #

## 3.1 思路 ##

1.  用一个Map记录每个独立数字对应出现次数
2.  再用HashSet记录所有出现次数并去重
3.  最后比较独立数字个数和去重后的出现次数，相等则说明所有独立数字出现次数都不同

## 3.2 代码 ##

class Solution { 
        public boolean uniqueOccurrences(int[] arr) { 
            // 记录每个独立数字对应出现次数
            Map<Integer,Integer> countMap = new HashMap<>();
            
            for(int i = 0; i < arr.length; i++){ 
                Integer count = countMap.get(arr[i]);
                if(count == null){ 
                    // 该数字未出现过
                    countMap.put(arr[i], 1);
                } else{ 
                    // 该数字已经出现过
                    countMap.put(arr[i], count + 1);
                }
            }
            // 记录所有出现次数并去重
            Set<Integer> distinctSet = new HashSet<>();
            countMap.values().stream().forEach(distinctSet::add);
            
            // 比较独立数字个数和去重后的出现次数，相等说明所有独立数字出现次数都不同
            return distinctSet.size() == countMap.size();
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20201028105504725.png_pic_center]

O(N)

因为使用HashMap，会有一些对象创建、查找、冲突等开销

## 3.4 空间复杂度 ##

O©

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/4adc05e7a5544561accb6d517d9eebef.png
[20201028102358318.png_pic_center]: /images/20221120/37836019f4f549c6a96e586b9a5ae97a.png
[20201028105504725.png_pic_center]: /images/20221120/070c565e061c423ab4feab9ab50d01a4.png