[LeetCode & 剑指 offer 刷题笔记] 目录 (持续更新中...)
Contains Duplicate
Given an array of integers, find if the array contains any duplicates.
- Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
- Example 1:
- Input: [1,2,3,1]
- Output: true
- Example 2:
- Input: [1,2,3,4]
- Output: false
- Example 3:
- Input: [1,1,1,3,3,4,3,2,4,2]
- Output: true
- /*
- 问题: 判断一个数组是否含重复元素
- 方法: 用 map 统计每个元素出现的次数
- O(n),O(n)
- 改进, 可以 sort 后判断, 这样就不需要额外空间了, 用时间换空间
- */
- #include <map>
- class Solution
- {
- public:
- bool containsDuplicate(vector<int>& nums)
- {
- unordered_map<int,int> dict;// 用 hash 表, 平均访问时间为 O(1)(用 unordered_set 也可以)
- for(int num:nums) // 统计每个元素的出现次数
- {
- dict[num]++; // 首次调用 operator[] 以零初始化计数器
- if(dict[num]> 1) return true;
- }
- return false;
- }
- };
来源: http://www.bubuko.com/infodetail-2909388.html