菜鸟起航。
题目(LeetCode No.217)
for循环遍历
初看极为简单，不动脑就会去选择两次for循环遍历对比。
class Solution {
public boolean containsDuplicate(int[] nums) {
for(int i=0;i<nums.length-1;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]==nums[j]){
return true;
}
}
}
return false;
}
}
O(n^2)的时间复杂度，着实是选择了一个最笨拙的解法。
初步的优化将整个数组排序之后再开始对比，由于无论是时间复杂度O(nlogn)的快排还是其他O(n)级别的排序算法，之后用一个for循环对i和i+1进行比较，O(n)+O(n)或者O(nlogn)+O(n)相对于一开始的O（n^2）都快了许多。
使用HashSet
还有一种思路是使用HashSet，效率相较于排序后比较的方式低。
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i : nums) {
if (set.contains(i)) return true;
set.add(i);
}
return false;
}
}
位运算
其实还看到了一种方式，是通过位运算来判重，速度很快。
但是事实上这种方式在本题有局限性，不能够满足所有情况。
class Solution {
public boolean containsDuplicate(int[] nums) {
if (nums.length < 1 || nums[0] == 237384 || nums[0] == -24500)
return false;
boolean[] bs = new boolean[1024];
for (int n : nums)
if (bs[n & 1023])
return true;
else
bs[n & 1023] = true;
return false;
}
}