算法练习第二天——存在重复元素
算法练习第二天——存在重复元素
存在重复元素题目
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例一：
输入： nums = [1,2,3,2]
输出： true
示例二：
输入： nums = [1,2,3,4]
输出： false
示例三：
输入： nums = [1,2,1,3,3,4,3,2,4,2]
输出： true
解题思路
方法一：排序
在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中，因此我们可以先对数组进行排序，然后再判断是否存在相邻位置有相同的数，若有则存在重复元素，反之，则不存在重复元素。
代码以golang为例子：
func ifinit(nums []int) bool { var temp int for i := 1;i < len(nums);i++{ if nums[i-1] > nums[i]{ temp = nums[i-1] num[i-1] = num[i] num[i] = temp } } for i := 1; i < len(nums); i++ { if nums[i] == nums[i-1] { return true } } return false }
上诉代码使用了冒泡排序对数组进行从小到大排序，代码量较大，因此我们可以使用sort方法直接对数组(切片)进行排序。
func ifinit(nums []int) bool { sort.Ints(nums) for i := 1; i < len(nums); i++ { if nums[i] == nums[i-1] { return true } } return false }
该解法复杂度
时间复杂度：O(N log N)O(NlogN)，其中 N 为数组的长度。
空间复杂度：O(log N)O(logN)，其中 N 为数组的长度。
方法二：哈希表
对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素，反之则不存在重复元素。
func ifinit(nums []int) bool { temp := map[int]int{} for _, i := range nums { if _, j := temp[i]; j { return true } temp[i] += 1 } return false }
复杂度分析
- 时间复杂度：O(N)，其中 N 为数组的长度。
- 空间复杂度：O(N)，其中 N 为数组的长度。
