文章目錄

• 前言
• 一、題目描述
• 二、思路
• • 1.暴力破解
  • 2.空間換時(shí)間（有點(diǎn)像桶排序思想）
  • 3，排序
• 總結(jié)

---

前言

??????本系列文章為leetCode刷題筆記，僅供參考。

一、題目描述

給定一個(gè)整數(shù)數(shù)組，判斷是否存在重復(fù)元素。

如果存在一值在數(shù)組中出現(xiàn)至少兩次，函數(shù)返回 true 。如果數(shù)組中每個(gè)元素都不相同，則返回 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
見(jiàn)：https://leetcode-cn.com/problems/contains-duplicate/

二、思路

1.暴力破解

??????對(duì)該數(shù)組遍歷，依次判斷是否有無(wú)重復(fù)元素，時(shí)間復(fù)雜度為O(n2),空間復(fù)雜度為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.空間換時(shí)間（有點(diǎn)像桶排序思想）

??????采用一個(gè)臨時(shí)數(shù)組來(lái)標(biāo)記原數(shù)組中元素出現(xiàn)次數(shù)，但是沒(méi)有考慮到有負(fù)整數(shù)的存在，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為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下標(biāo)可用，申請(qǐng)空間需大于maxN。for(int i=0;i<nums.length;i++){tmp[nums[i]]+=1;if(tmp[nums[i]]==2)return true;}return false;}

3，排序

??????先排序（ologn），再判斷是否存在重復(fù)元素。時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(logn)，這里取得是遞歸調(diào)用棧的深度，（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;}

---

總結(jié)

??????假設(shè)空間復(fù)雜度不做限制，且不采用排序，是否有時(shí)間復(fù)雜度低于O(n2)的解法呢？

總結(jié)

以上是生活随笔為你收集整理的LeetCode算法题1：判断整数数组是否存在重复元素的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。