287 Find the Duplicate Number¶

:::tip Could be solved by

Binary Search \(O(NlogN)\)
Linked list \(O(N)\) :::

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

Input: nums = [1,1]
Output: 1

Example 4:

Input: nums = [1,1,2]
Output: 1

Sorting and finding duplicate¶

Use merge sort or quick sort

Time complexity: O(NLogN) Space complexity: O(1)

Using Dictionary¶

Time complexity: O(N) Space complexity: O(N)

Linked list cycle¶

Convert the problem to find the entry point of the cycle in a linked list.

Take the number in the array as the index of next node.

[1,3,4,2,2]

0->1->3->2->4->2 cycle: 2->4->2

[3,1,3,4,2]

0->3->4->2->3->4->2 cycle 3->4->2->3

Time complexity: O(N) Space complexity: O(1)

C# Solution Linked List¶

using System;
using System.Collections.Generic;

namespace Algorithms.Medium
{
  public class FindDuplicateNumberLL
  {
    public static int Find(int[] vs)
    {
      int slow = 0, fast = 0;
      while (true)
      {
        slow = vs[slow];
        fast = vs[vs[fast]];
        if (slow == fast) break;
      }
      fast = 0;
      while (fast != slow)
      {
        slow = vs[slow];
        fast = vs[fast];
      }

      return slow;
    }
  }
}

C# Tests Linked List¶

using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class FindDuplicateNumberLLTests
  {
    [Fact]
    public void TestLL()
    {
      Assert.Equal(2, FindDuplicateNumberLL.Find(new int[] { 1, 3, 4, 2, 2 }));
      Assert.Equal(3, FindDuplicateNumberLL.Find(new int[] { 3, 1, 3, 4, 2 }));
      Assert.Equal(1, FindDuplicateNumberLL.Find(new int[] { 1, 1 }));
      Assert.Equal(1, FindDuplicateNumberLL.Find(new int[] { 1, 1, 2 }));
    }
  }
}

Linked list explanation

Binary Search¶

Find the smallest m such that len(nums <= m) > m, which means m is the duplicate number.

In the sorted form [1, 2, …, m1, m2, m + 1, …, n]

There are m+1 numbers <= m

Time complexity: O(logN) Space complexity: O(1)

C# Solution Binary Search¶

using System;
using System.Collections.Generic;

namespace Algorithms.Medium
{
  public class FindDuplicateNumberBS
  {
    public static int Find(int[] vs)
    {
      int l = 0, r = vs.Length - 1;

      while (l < r)
      {
        var pivot = (r - l) / 2 + l;

        var count = 0;
        foreach (var num in vs)
        {
          if (num <= pivot) count++;
        }

        if (count <= pivot)
        {
          l = pivot + 1;
        }
        else
        {
          r = pivot;
        }
      }

      return l;
    }
  }
}

C# Tests Binary Search¶

using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class FindDuplicateNumberBSTests
  {
    [Fact]
    public void TestBS()
    {
      Assert.Equal(2, FindDuplicateNumberBS.Find(new int[] { 1, 3, 4, 2, 2 }));
      Assert.Equal(3, FindDuplicateNumberBS.Find(new int[] { 3, 1, 3, 4, 2 }));
      Assert.Equal(1, FindDuplicateNumberBS.Find(new int[] { 1, 1 }));
      Assert.Equal(1, FindDuplicateNumberBS.Find(new int[] { 1, 1, 2 }));
    }
  }
}