文章目录
前言一、题目描述二、思路1.暴力破解2.空间换时间(有点像桶排序思想)3,排序总结前言
本系列文章为leetCode刷题笔记,仅供参考。
一、题目描述
给定一个整数数组,判断是否存在重复元素。
如果存在一值在数组中出现至少两次,函数返回 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
见:https://leetcode-/problems/contains-duplicate/
二、思路
1.暴力破解
对该数组遍历,依次判断是否有无重复元素,时间复杂度为O(n2),空间复杂度为O(1)。(Fail)
代码如下:
class Solution {public boolean 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;}}
2.空间换时间(有点像桶排序思想)
采用一个临时数组来标记原数组中元素出现次数,但是没有考虑到有负整数的存在,时间复杂度为O(n),空间复杂度为O(m)。(Fail)
代码如下:
public boolean containsDuplicate(int[] nums){int maxN=Integer.MIN_VALUE;for(int i=0;i<nums.length;i++){if(nums[i]>maxN)maxN=nums[i];}int[] tmp=new int[maxN+1]; //要想后面的maxN下标可用,申请空间需大于maxN。for(int i=0;i<nums.length;i++){tmp[nums[i]]+=1;if(tmp[nums[i]]==2)return true;}return false;}
3,排序
先排序(ologn),再判断是否存在重复元素。时间复杂度为O(nlogn),空间复杂度为O(logn),这里取得是递归调用栈的深度,(Pass)
代码如下:
public boolean containsDuplicate(int[] nums){Arrays.sort(nums);for(int i=0;i<nums.length-1;i++){if(nums[i]==nums[i+1])return true;}return false;}
总结
假设空间复杂度不做限制,且不采用排序,是否有时间复杂度低于O(n2)的解法呢?