在计算机领域,算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始,跟随我每天刷一道算法题吧!


LeetCode #217 存在重复元素

题目

给定一个整数数组,判断是否存在重复元素。

如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

示例1:

输入: [1,2,3,1]
输出: true

示例2:

输入: [1,2,3,1]
输出: true

示例3:

输入: [1,2,3,1]
输出: true

解题思路

题目要求:判断数组是否有两个相同的元素。

思路1:

这道题和 #1 两数之和 十分的像,都是在数组中寻找符合某条件的两个元素。

所以我们可以照搬 #1 两数之和 的思路进行解题。

1. for循环遍历每一个元素,在map中查找与该元素符合条件的元素。

2. 如果map中没有符合条件的元素,则将该元素放入map中。

3. 为下一个元素寻找符合条件的元素。

哈希遍历代码:

class Solution {
public boolean containsDuplicate(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int length = nums.length;

for (int i = 0; i < length; i++){
if (map.containsKey(nums[i])){
return true;
}
map.put(nums[i], i);
}
return false;
}
}

改进:

思路1显然是可行的,但不是最优的办法。

首先,使用map需要开辟额外的内存空间;其次,对于元素比较少的数组,map在维护其属性的开销比例更大。

所以,我们需要思考不使用map的办法。

思路2

问题又回到了如何寻找两个相同的元素。

既然这两个元素是相同的,那么在有序数组中,相同的元素必然是相邻的。

这样我们只需要在有序的数组中判断相邻的元素是否相同即可。

1. 对数组进行排序。

2. 遍历数组,判断当前元素与下一个元素是否相同。

排序查找代码:

class Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
int length = nums.length;

for (int i = 0; i < length - 1; i++){
if (nums[i] == nums[i + 1]){
return true;
}
}
return false;
}
}

评论