[算法]存在重复元素
上一篇 /
下一篇 2019-05-30 11:33:48 / 天气: 阴雨
/ 心情: 平静
/ 个人分类:算法
最近在准备面试,学习到不少算法题目。希望总结下来,在以后的工作中有所帮助,提升自己的能力。
问题一:
给定一个整数数组,判断是否存在重复元素。如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
思路1:
以我的初级编程水平,第一个思路是用双层for循环,不考虑空间复杂度和时间复杂度。以JAVA代码为例:
class Solution {
public boolean containsDuplicate(int[] nums) {
int index1 = 0;
int index2 = 0;
int len = nums.length;
System.out.println("len is: " + len); //for debugging
int target = 0;
int next = 0;
for(index1 = 0; index1<len; index1++){
for(index2 = index1+1; index2<len; index2++){
target = nums[index1];
System.out.println("previous is:" + target);//for debugging
next = nums[index2];
System.out.println("next is:" + next);//for debugging
if(target==next)
return true;
else
continue;
}
}
return false;
}
}
现在增加题目要求,“不得嵌套循环,不得使用递归”。如此,上述JAVA代码就不符合要求了,并且在leetcode上提交执行以后显示“超出时间限制”。
思路2:
若将题目变为:
给定一个整数数组,判断是否存在重复元素。如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。
不得嵌套循环,且需要保证额外的空间复杂度为O(1),则需要考虑使用“堆”排序。//TBD
收藏
举报
TAG: