LeetCode Meditations: Contains Duplicate

LeetCode Meditations (79 Part Series)

For this problem, let’s start with the description:

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

For example:


<span>[</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>1</span><span>]</span> <span>// true</span>
<span>[</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>]</span> <span>// false</span>
<span>[</span><span>1</span><span>,</span> <span>1</span><span>,</span> <span>1</span><span>,</span> <span>3</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>3</span><span>,</span> <span>2</span><span>,</span> <span>4</span><span>,</span> <span>2</span><span>]</span> <span>// true</span>
<span>[</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>1</span><span>]</span> <span>// true</span>
<span>[</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>]</span> <span>// false</span>
<span>[</span><span>1</span><span>,</span> <span>1</span><span>,</span> <span>1</span><span>,</span> <span>3</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>3</span><span>,</span> <span>2</span><span>,</span> <span>4</span><span>,</span> <span>2</span><span>]</span> <span>// true</span>
[1, 2, 3, 1] // true
[1, 2, 3, 4] // false
[1, 1, 1, 3, 3, 4, 3, 2, 4, 2] // true

Enter fullscreen mode Exit fullscreen mode

We can use a Set which only keeps the values without duplicates.

For each example, it would look like this:


<span>new</span> <span>Set</span><span>([</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>1</span><span>]);</span>
<span>// -> Set(3) { 1, 2, 3 }</span>
<span>new</span> <span>Set</span><span>([</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>]);</span>
<span>// -> Set(4) { 1, 2, 3, 4 }</span>
<span>new</span> <span>Set</span><span>([</span><span>1</span><span>,</span> <span>1</span><span>,</span> <span>1</span><span>,</span> <span>3</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>3</span><span>,</span> <span>2</span><span>,</span> <span>4</span><span>,</span> <span>2</span><span>]);</span>
<span>// -> Set(4) { 1, 3, 4, 2 }</span>
<span>new</span> <span>Set</span><span>([</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>1</span><span>]);</span>
<span>// -> Set(3) { 1, 2, 3 }</span>

<span>new</span> <span>Set</span><span>([</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>]);</span>
<span>// -> Set(4) { 1, 2, 3, 4 }</span>

<span>new</span> <span>Set</span><span>([</span><span>1</span><span>,</span> <span>1</span><span>,</span> <span>1</span><span>,</span> <span>3</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>3</span><span>,</span> <span>2</span><span>,</span> <span>4</span><span>,</span> <span>2</span><span>]);</span>
<span>// -> Set(4) { 1, 3, 4, 2 }</span>
new Set([1, 2, 3, 1]);
// -> Set(3) { 1, 2, 3 }

new Set([1, 2, 3, 4]);
// -> Set(4) { 1, 2, 3, 4 }

new Set([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]);
// -> Set(4) { 1, 3, 4, 2 }

Enter fullscreen mode Exit fullscreen mode

In that case, the difference between the size of the set and the length of the original array will tell us whether it contains duplicates or not. If they are not equal to each other, that means the array has duplicates.

Using TypeScript, my solution was this:


<span>function</span> <span>containsDuplicate</span><span>(</span><span>nums</span><span>:</span> <span>number</span><span>[]):</span> <span>boolean</span> <span>{</span>
  <span>return</span> <span>!</span><span>(</span><span>new</span> <span>Set</span><span>(</span><span>nums</span><span>).</span><span>size</span> <span>===</span> <span>nums</span><span>.</span><span>length</span><span>);</span>
<span>};</span>
<span>function</span> <span>containsDuplicate</span><span>(</span><span>nums</span><span>:</span> <span>number</span><span>[]):</span> <span>boolean</span> <span>{</span>
  <span>return</span> <span>!</span><span>(</span><span>new</span> <span>Set</span><span>(</span><span>nums</span><span>).</span><span>size</span> <span>===</span> <span>nums</span><span>.</span><span>length</span><span>);</span>
<span>};</span>
function containsDuplicate(nums: number[]): boolean {
  return !(new Set(nums).size === nums.length);
};

Enter fullscreen mode Exit fullscreen mode

It’s obvious from the size and length comparison that this solution works, and indeed, it passes the tests.

Time & space complexity

My guess for the time complexity is that it’s O ( n ) O(n) O(n) , because the Set constructor iterates over each element in the array it is given as the argument.
I think that the space complexity is also O ( n ) O(n) O(n) , because in the worst case where each element is unique, Set needs to allocate memory for each of them.

Using Python

We can translate this solution into Python like this as well:


<span>class</span> <span>Solution</span><span>:</span>
    <span>def</span> <span>containsDuplicate</span><span>(</span><span>self</span><span>,</span> <span>nums</span><span>:</span> <span>List</span><span>[</span><span>int</span><span>])</span> <span>-></span> <span>bool</span><span>:</span>
        <span>return</span> <span>len</span><span>(</span><span>set</span><span>(</span><span>nums</span><span>))</span> <span>!=</span> <span>len</span><span>(</span><span>nums</span><span>)</span>
<span>class</span> <span>Solution</span><span>:</span>
    <span>def</span> <span>containsDuplicate</span><span>(</span><span>self</span><span>,</span> <span>nums</span><span>:</span> <span>List</span><span>[</span><span>int</span><span>])</span> <span>-></span> <span>bool</span><span>:</span>
        <span>return</span> <span>len</span><span>(</span><span>set</span><span>(</span><span>nums</span><span>))</span> <span>!=</span> <span>len</span><span>(</span><span>nums</span><span>)</span>
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) != len(nums)

Enter fullscreen mode Exit fullscreen mode

It’s now time to take a breath.

Let’s look at NeetCode’s solution:


<span>class</span> <span>Solution</span><span>:</span>
    <span>def</span> <span>containsDuplicate</span><span>(</span><span>self</span><span>,</span> <span>nums</span><span>:</span> <span>List</span><span>[</span><span>int</span><span>])</span> <span>-></span> <span>bool</span><span>:</span>
        <span>hashset</span> <span>=</span> <span>set</span><span>()</span>
        <span>for</span> <span>n</span> <span>in</span> <span>nums</span><span>:</span>
            <span>if</span> <span>n</span> <span>in</span> <span>hashset</span><span>:</span>
                <span>return</span> <span>True</span>
            <span>hashset</span><span>.</span><span>add</span><span>(</span><span>n</span><span>)</span>
        <span>return</span> <span>False</span>
<span>class</span> <span>Solution</span><span>:</span>
    <span>def</span> <span>containsDuplicate</span><span>(</span><span>self</span><span>,</span> <span>nums</span><span>:</span> <span>List</span><span>[</span><span>int</span><span>])</span> <span>-></span> <span>bool</span><span>:</span>
        <span>hashset</span> <span>=</span> <span>set</span><span>()</span>

        <span>for</span> <span>n</span> <span>in</span> <span>nums</span><span>:</span>
            <span>if</span> <span>n</span> <span>in</span> <span>hashset</span><span>:</span>
                <span>return</span> <span>True</span>
            <span>hashset</span><span>.</span><span>add</span><span>(</span><span>n</span><span>)</span>

        <span>return</span> <span>False</span>
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hashset = set()

        for n in nums:
            if n in hashset:
                return True
            hashset.add(n)

        return False

Enter fullscreen mode Exit fullscreen mode

The worst case is still O ( n ) O(n) O(n) , and space complexity is O ( n ) O(n) O(n) as well in the case of each element being unique.

However, I think it’s an improvement as compared to my initial solution, because instead of creating the set in one go, we can return immediately if the element is in the set as we go through adding each one.

As we have reached the end of this meditation, we can take one more deep breath. Next up is the Valid Anagram problem. Until then, happy coding.

LeetCode Meditations (79 Part Series)

原文链接：LeetCode Meditations: Contains Duplicate

展开阅读全文

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END