leetcode Contains Duplicate 整理

本次题解包括:

  • 217 Contains Duplicate
  • 219 Contains Duplicate II
  • 220 Contains Duplicate III

217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

题目地址: leetcode Contains Duplicate

题意:给定一个数组,求它是否有重复的元素

思路:Hash

Python

写成oneline也行

C++

Java

 

 

219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

题目地址: leetcode Contains Duplicate II

题意,给定一个数组和整数k,问数组中是否有i – j <=k 并且nums[i] == nums[j]的两个不同的下标

思路:同样的hash,记录下标即可

C++

Java

Python

 

 

220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] andnums[j] is at most t and the difference between i and j is at most k.

题目地址: leetcode Contains Duplicate III

题意:给定一个数组和两个整数t 和k ,求是否有不同的两个下标i和j,满足|nums[i] – nums[j]|<= t && | i – j | <=k

思路:

方法1

平衡树的方法。复杂度O(nlogk)

题意有:-t <= x- nums[i] <= t

左边有 nums[i]  – t <= x 因此把符合条件的数构建成一颗平衡树,然后查找一个最小的x使得x>= nums[i] – t

如果该x还满足 x  <= t + nums[i]就是我们要的答案啦

Java

 

方法2

桶的方法 O(n)

思想是以t+1为间隔来分桶,对于一个数,将其分到第key = num / (t + 1) 个桶中,我们只需要查找相同的和相邻的桶的元素就可以判断有无重复。

比如t = 4,那么0~4为桶0,5~9为桶1,10~14为桶2 。

使用t+1个桶是为啥?这是为了避免除以0的错误,可能t = 0.

下面,C++和Java的版本,如果num为负数,那么key -= 1,因为比C++/Java 的负数取整是:-2 /3 = 0,这题这样是不行的。

而Python则OK, -2 // 3 = -1。

 

C++

Java

Python

 

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Contains Duplicate 整理
本文地址:https://www.hrwhisper.me/leetcode-contains-duplicate-i-ii-iii/

听说长得好看的已经打赏了

Leetcode , . permalink.

2 thoughts on “leetcode Contains Duplicate 整理

  1. 一些疑问和简介:
    “方法2

    桶的方法 O(n)

    思想是分成t+1个桶,对于一个数,将其分到第key = num / (t + 1) 个桶中,我们只需要查找相同的和相邻的桶的元素就可以判断有无重复。

    比如t = 4,那么0~4为桶0,5~9为桶1,10~14为桶2 。

    使用t+1个桶是为啥?这是为了避免除以0的错误,可能t = 0.

    下面,C++和Java的版本,如果num为负数,那么key -= 1,因为比C++/Java 的负数取整是:-2 /3 = 0,这题这样是不行的。

    而Python则OK, -2 // 3 = -1。”

    这里有两处疑问:
    1.不是“思想是分成t+1个桶”,是不是应该是“思想是以t+1为间隔来分桶”。t+1是桶的容量才对;
    2.用t+1不只是因为处理0的情况吧,而是为了让桶内最大数与最小数的差值为t。如果除以t的话, 桶内最大数与最小数的差值就为t-1了,会出错

    • 第一个疑问是我表达不清楚,是你说的那样 以t + 1为间隔分桶。
      第二个疑问: t + 1是为了处理0的情况。题目是最大最小数差值至多为t,而不是要就等于t。

Leave a Reply

Your email address will not be published. Required fields are marked *