C#LeetCode刷题之#217-存在重复元素(Contains Duplicate)
问题
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3772 访问。
给定一个整数数组,判断是否存在重复元素。
如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。
输入: [1,2,3,1]
输出: true
输入: [1,2,3,4]
输出: false
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
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.
Input: [1,2,3,1]
Output: true
Input: [1,2,3,4]
Output: false
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true
示例
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3772 访问。
public class Program {
public static void Main(string[] args) {
int[] nums = null;
nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 7 };
var res = ContainsDuplicate(nums);
Console.WriteLine(res);
nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };
res = ContainsDuplicate2(nums);
Console.WriteLine(res);
nums = new int[] { 1, 2, 3, 3, 5, 6, 7, 8 };
res = ContainsDuplicate3(nums);
Console.WriteLine(res);
Console.ReadKey();
}
private static bool 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;
}
private static bool ContainsDuplicate2(int[] nums) {
//先排序,再使用单循环比较相邻值
Array.Sort(nums);
for(int i = 0; i < nums.Length - 1; i++) {
if(nums[i] == nums[i + 1]) return true;
}
return false;
}
private static bool ContainsDuplicate3(int[] nums) {
//哈希法
var dic = new Dictionary<int, int>();
foreach(var num in nums) {
if(dic.ContainsKey(num)) return true;
dic[num] = 0;
}
return false;
}
}
以上给出3种算法实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3772 访问。
True
False
True
分析:
显而易见,ContainsDuplicate的时间复杂度为: ,ContainsDuplicate2的时间复杂度需要考虑Array.Sort()具体使用的排序算法,ContainsDuplicate3的时间复杂度为: 。
最新文章
- Ceph剖析:数据分布之CRUSH算法与一致性Hash
- Combination Sum II Combinations
- 济南学习D2T2__数学分析题
- offset笔记
- nyoj 19擅长排列的小明 (DFS)
- Grid Infrastructure Single Client Access Name (SCAN) Explained (文档 ID 887522.1)
- rhel5.5 Oracle10g安装记录
- 用vim处理字符的大小写转换
- winForm帮助信息
- C、C++中引用与指针的区别
- EF实例创建问题
- 基于RTMP的实时流媒体的QoE分析
- Java集合框架之二:LinkedList源码解析
- Spring Boot日志集成实战
- 对delphi中的数据敏感控件的一点探索
- ROS学习(六)—— 理解ROS节点
- C#:添加web service引用
- Windows 2008开启远程桌面连接
- JSP中forEach和forTokens循环的用法
- [BZOJ5109]大吉大利,晚上吃鸡!
热门文章
- java中int相除取小数点后两位或限定位数
- T133316 57级返校测试重测-T4-字符串的修改
- layui 魔改:富文本编辑器添加上传视频功能
- 05 ES6模块化规范基础详解
- DJANGO-天天生鲜项目从0到1-005-FastDFS与Nginx打造自定义文件存储系统
- asp.net core 3 使用nlog日志组件,使用$ {basedir}保存位置不对,记录下怎么解决
- Mysql concat() group_concat()用法
- C#结合SMTP实现邮件报警通知
- MyBatis--动态插入多条数据
- 第一章 Java快速入门