LeetCode 30 days Challenge - Day 7
本系列将对LeetCode新推出的30天算法挑战进行总结记录,旨在记录学习成果、方便未来查阅,同时望为广大网友提供帮助。
Counting Elements
Given an integer array arr
, count element x
such that x + 1
is also in arr
.
If there’re duplicates in arr
, count them seperately.
Example 1:
1 | Input: arr = [1,2,3] |
Example 2:
1 | Input: arr = [1,1,3,3,5,5,7,7] |
Example 3:
1 | Input: arr = [1,3,2,3,5,0] |
Example 4:
1 | Input: arr = [1,1,2,2] |
Constraints:
1 <= arr.length <= 1000
0 <= arr[i] <= 1000
Solution
题目要求分析:给定一个字符串数组,对任一元素x,如果x+1也在数组中,记一次数。对多个相同元素x,分开计算次数。
解法:
使用unordered_map
哈希结构进行计数,即:
建立一个由映射:
unordered_map<int, int> m;
对题目给出的数组,遍历之,m的键值代表出现的元素,每个键对应的值记录其出现次数(因为若满足计数条件,相同元素要分开考虑,故此处记录了每个元素出现的次数)。
遍历m,判断并更新res即可:
for (auto v : m) if (m.count(v.first + 1)) res += v.second;
(此处操作可以参考“对unordered_map进行遍历”)
(注意,此处
map.count()
不为0即“x+1也在数组中”)
1 | int countElements(vector<int>& arr) { |
Karl