problem287

package
Version: v1.6.5 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Mar 23, 2021 License: MIT Imports: 0 Imported by: 0

README

< Previous                  Next >

287. Find the Duplicate Number (Medium)

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

 

Constraints:

  • 2 <= n <= 3 * 104
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • All the integers in nums appear only once except for precisely one integer which appears two or more times.

 

Follow up:

  • How can we prove that at least one duplicate number must exist in nums?
  • Can you solve the problem without modifying the array nums?
  • Can you solve the problem using only constant, O(1) extra space?
  • Can you solve the problem with runtime complexity less than O(n2)?

[Array] [Two Pointers] [Binary Search]

Similar Questions

  1. First Missing Positive (Hard)
  2. Single Number (Easy)
  3. Linked List Cycle II (Medium)
  4. Missing Number (Easy)
  5. Set Mismatch (Easy)

Documentation

The Go Gopher

There is no documentation for this package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
t or T : Toggle theme light dark auto
y or Y : Canonical URL