花花酱 LeetCode 80. Remove Duplicates from Sorted Array II

By zxi on September 30, 2019

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Solution:

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

C++

// Author: Huahua

class Solution {

public:

int removeDuplicates(vector<int>& nums) {

const int n = nums.size();

if (n <= 2) return n;

int index = 1;

int len = 1;

int last = nums[0];

while (index < n) {

int count = 1;

while (index < n && nums[index] == last) {

++count;

++index;

}

if (count >= 2) nums[len++] = last;

if (index < n) {

last = nums[index++];

nums[len++] = last;

}

return len;

}

};

花花酱 LeetCode 217. Contains Duplicate

By zxi on July 22, 2019

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.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Solution 1: HashTable

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 48ms/16.5MB

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

unordered_set<int> s;

for (int num : nums)

if (!s.insert(num).second) return true;

return false;

}

};

Solution 2: Sorting

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

C++

// Author: Huahua, 28ms/11.4MB

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

sort(begin(nums), end(nums));

for (int i = 1; i < nums.size(); ++i)

if (nums[i] == nums[i - 1]) return true;

return false;

}

};

花花酱 LeetCode 287. Find the Duplicate Number

By zxi on July 14, 2018

Problem

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

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

Example 2:

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

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n²).
There is only one duplicate number in the array, but it could be repeated more than once.

Solution1: Binary Search

Time complexity: O(nlogn)

Space complexity: O(1)

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

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int findDuplicate(vector<int>& nums) {

int l = 1;

int r = nums.size();

while (l < r) {

int m = (r - l) / 2 + l;

int count = 0; // len(nums <= m)

for (int num : nums)

if (num <= m) ++count;

if (count <= m)

l = m + 1;

else

r = m;

}

return l;

}

};

Solution: 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)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int findDuplicate(vector<int>& nums) {

int slow = 0;

int fast = 0;

while (true) {

slow = nums[slow];

fast = nums[nums[fast]];

if (slow == fast) break;

}

fast = 0;

while (fast != slow) {

slow = nums[slow];

fast = nums[fast];

}

return slow;

}

};

Posts tagged as “duplicate”

花花酱 LeetCode 80. Remove Duplicates from Sorted Array II

Solution:

C++

Related Problems

花花酱 LeetCode 217. Contains Duplicate

Solution 1: HashTable

C++

Solution 2: Sorting

C++

花花酱 LeetCode 287. Find the Duplicate Number

Problem

Solution1: Binary Search

Solution: Linked list cycle

Posts tagged as “duplicate”

花花酱 LeetCode 80. Remove Duplicates from Sorted Array II

Solution:

C++

Related Problems

花花酱 LeetCode 82. Remove Duplicates from Sorted List II

Solution:

C++

Related Problems

花花酱 LeetCode 83. Remove Duplicates from Sorted List

Solution:

C++

花花酱 LeetCode 217. Contains Duplicate

Solution 1: HashTable

C++

Solution 2: Sorting

C++

花花酱 LeetCode 287. Find the Duplicate Number

Problem

Solution1: Binary Search

Solution: Linked list cycle