LEETCODE 1426. Counting Elements 解题思路分析

题目大意:

Given an integer array arr, count how many elements x there are, such that x + 1 is also in arr.

If there’re duplicates in arr, count them seperately.

Example 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Example 3:

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Example 4:

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

Example 5:

Input: arr = [1,1,2]
Output: 2
Explanation: Both 1s are counted because 2 is in the array.

Constraints:

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

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

解题思路分析:

  1. 首先遍历一遍数组,统计每种数字的个数。记录在Map中,key为数字,value为该数字出现的个数。
  2. 遍历map中的每一个key(数字),对于当前数字,如果map中存在值为key+1的key的话,那么当前key所代表的数字就是一个符合答案的数,将他的个数累加至返回结果。

实现代码:

public int countElements(int[] arr) {
    // 统计数组中每个数字的个数
    Map<Integer, Integer> map = new HashMap<>();
    for(int num : arr){
        int count=map.getOrDefault(num,0);
        map.put(num,count+1);
    }
    // 返回结果
    int res=0;
    // 循环map中的key(所有不重复的数字)
    for(int num : map.keySet()){
        // 如果存在num+1,说明当前数字是符合题意的数字
        if(map.containsKey(num+1)){
            // 将当前数字的个数累加至返回结果
            res+=map.get(num);
        }
    }
    return res;
}

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

Runtime: 1 ms, faster than 87.53% of Java online submissions for Counting Elements.

Memory Usage: 37.2 MB, less than 100.00% of Java online submissions for Counting Elements.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1426-counting-elements-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。