217. Contains Duplicate【easy】
217. Contains Duplicate【easy】
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.
解法一：
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
if (nums.empty()) {
return false;
}
unordered_map<int, int> my_map;
for (int i = ; i < nums.size(); ++i) {
if (++my_map[nums[i]] > ) {
return true;
}
}
return false;
}
};
解法二：
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
return nums.size() > set<int>(nums.begin(), nums.end()).size();
}
};
参考@chammika 的代码
解法三：
public boolean containsDuplicate(int[] nums) {
for(int i = 0; i < nums.length; i++) {
for(int j = i + 1; j < nums.length; j++) {
if(nums[i] == nums[j]) {
return true;
}
}
}
return false;
}
Time complexity: O(N^2), memory: O(1)
The naive approach would be to run a iteration for each element and see whether a duplicate value can be found: this results in O(N^2) time complexity.
解法四：
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for(int ind = 1; ind < nums.length; ind++) {
if(nums[ind] == nums[ind - 1]) {
return true;
}
}
return false;
}
Time complexity: O(N lg N), memory: O(1) - not counting the memory used by sort
Since it is trivial task to find duplicates in sorted array, we can sort it as the first step of the algorithm and then search for consecutive duplicates.
解法五：
public boolean containsDuplicate(int[] nums) {
final Set<Integer> distinct = new HashSet<Integer>();
for(int num : nums) {
if(distinct.contains(num)) {
return true;
}
distinct.add(num);
}
return false;
}
Time complexity: O(N), memory: O(N)
Finally we can used a well known data structure hash table that will help us to identify whether an element has been previously encountered in the array.
解法三、四、五均参考@jmnarloch 的代码
最新文章
- WebClient 访问https
- Java返回距离当前时间段
- POI设置边框
- IIS管理网站浏览
- spark概论，补充
- Android中Cursor（游标）类的概念和用法
- Tomcat配置随笔
- 编译android的linux kernel goldfish
- 基于visual Studio2013解决C语言竞赛题之1045打印成绩
- HTML+CSS - 搜索 And 高级搜索
- 2、创建File类对象
- 为ubuntu添加右键打开终端效果
- 查看selenium API
- 获取百度地图POI数据二（准备搜索关键词）
- Django之破解数独
- FB05付款清帐Function
- C语言实现二叉排序树
- 如何将hdf5文件转换成tflite文件
- 查看和设置Oracle数据库字符集
- 打印sql语句方法