Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.Return k.Custom Judge:The judge will test your solution with the following code:int[] nums = [...]; // Input arrayint[] expectedNums = [...]; // The expected answer with correct lengthint k = removeDuplicates(nums); // Calls your implementationassert k == expectedNums.length;for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i];}If all assertions pass, then your solution will be accepted. Example 1:Input: nums = [1,1,2]Output: 2, nums = [1,2,_]Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.It does not matter what you leave beyond the returned k (hence they are underscores).Example 2:Input: nums = [0,0,1,1,1,2,2,3,3,4]Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.It does not matter what you leave beyond the returned k (hence they are underscores). Constraints:1 <= nums.length <= 3 * 104-100 <= nums[i] <= 100nums is sorted in non-decreasing order.
Question
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.Return k.Custom Judge:The judge will test your solution with the following code:int[] nums = [...]; // Input arrayint[] expectedNums = [...]; // The expected answer with correct lengthint k = removeDuplicates(nums); // Calls your implementationassert k == expectedNums.length;for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i];}If all assertions pass, then your solution will be accepted. Example 1:Input: nums = [1,1,2]Output: 2, nums = [1,2,]Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.It does not matter what you leave beyond the returned k (hence they are underscores).Example 2:Input: nums = [0,0,1,1,1,2,2,3,3,4]Output: 5, nums = [0,1,2,3,4,,,,,]Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.It does not matter what you leave beyond the returned k (hence they are underscores). Constraints:1 <= nums.length <= 3 * 104-100 <= nums[i] <= 100nums is sorted in non-decreasing order.
Solution 1
This problem can be solved using a two-pointer technique. Here is a step-by-step guide on how to do it in Python:
-
Initialize two pointers,
iandj, both pointing to the first element of the array. -
Start a while loop that continues until
jreaches the end of the array. -
Inside the loop, if
nums[i]is equal tonums[j], incrementjto skip the duplicate. -
If
nums[i]is not equal tonums[j], incrementiand copy the value ofnums[j]tonums[i]. -
After the loop, return
i + 1, which is the number of unique elements.
Here is the Python code for the above steps:
def removeDuplicates(nums):
if not nums:
return 0
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i + 1
This function works by maintaining a slow runner (i) and a fast runner (j). As long as nums[i] equals nums[j], we increment j to skip the duplicate. When we encounter nums[j] not equal to nums[i], the duplicate run has ended so we must copy its value to nums[i + 1]. i is then incremented and we repeat the same process again until j reaches the end of array.
Solution 2
This problem can be solved using the two-pointer technique. Here are the steps:
-
Check if the length of the array is 0 or 1. If it is, return the length because an array of such length would either be empty or have no duplicates.
-
Initialize two pointers, i and j. Set i to 0.
-
Start a loop with j from 1 to the end of the array.
-
In the loop, compare the elements at index i and j. If they are not equal, increment i and replace the element at index i with the element at index j.
-
If the elements at index i and j are equal, just increment j.
-
Continue this process until j reaches the end of the array.
-
The length of the array without duplicates will be i + 1.
Here is the Python code for the above steps:
def removeDuplicates(nums):
if len(nums) == 0 or len(nums) == 1:
return len(nums)
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i + 1
This function works by maintaining a slow runner (i) and a fast runner (j). As long as nums[i] == nums[j], we increment j to skip the duplicate. When we encounter nums[j] != nums[i], the duplicate run has ended so we must copy its value to nums[i + 1]. i is then incremented and we repeat the same process again until j reaches the end of array.
Similar Questions
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.Return k after placing the final result in the first k slots of nums.Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
You are given an integer array nums. The uniqueness array of nums is the sorted array that contains the number of distinct elements of all the subarrays of nums. In other words, it is a sorted array consisting of distinct(nums[i..j]), for all 0 <= i <= j < nums.length.Here, distinct(nums[i..j]) denotes the number of distinct elements in the subarray that starts at index i and ends at index j.Return the median of the uniqueness array of nums.Note that the median of an array is defined as the middle element of the array when it is sorted in non-decreasing order. If there are two choices for a median, the smaller of the two values is taken. Example 1:Input: nums = [1,2,3]Output: 1Explanation:The uniqueness array of nums is [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])] which is equal to [1, 1, 1, 2, 2, 3]. The uniqueness array has a median of 1. Therefore, the answer is 1.Example 2:Input: nums = [3,4,3,4,5]Output: 2Explanation:The uniqueness array of nums is [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]. The uniqueness array has a median of 2. Therefore, the answer is 2.Example 3:Input: nums = [4,3,5,4]Output: 2Explanation:The uniqueness array of nums is [1, 1, 1, 1, 2, 2, 2, 3, 3, 3]. The uniqueness array has a median of 2. Therefore, the answer is 2. Constraints:1 <= nums.length <= 1051 <= nums[i] <= 105
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.Return k.Custom Judge:The judge will test your solution with the following code:int[] nums = [...]; // Input arrayint val = ...; // Value to removeint[] expectedNums = [...]; // The expected answer with correct length. // It is sorted with no values equaling val.int k = removeElement(nums, val); // Calls your implementationassert k == expectedNums.length;sort(nums, 0, k); // Sort the first k elements of numsfor (int i = 0; i < actualLength; i++) { assert nums[i] == expectedNums[i];}If all assertions pass, then your solution will be accepted. Example 1:Input: nums = [3,2,2,3], val = 3Output: 2, nums = [2,2,_,_]Explanation: Your function should return k = 2, with the first two elements of nums being 2.It does not matter what you leave beyond the returned k (hence they are underscores).Example 2:Input: nums = [0,1,2,2,3,0,4,2], val = 2Output: 5, nums = [0,1,4,0,3,_,_,_]Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.Note that the five elements can be returned in any order.It does not matter what you leave beyond the returned k (hence they are underscores). Constraints:0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
442. Find All Duplicates in an ArrayMediumTopicsCompaniesGiven an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.You must write an algorithm that runs in O(n) time and uses only constant extra space. Example 1:Input: nums = [4,3,2,7,8,2,3,1]Output: [2,3]Example 2:Input: nums = [1,1,2]Output: [1]Example 3:Input: nums = [1]Output: [] Constraints:n == nums.length1 <= n <= 1051 <= nums[i] <= nEach element in nums appears once or twice.
Remove Duplicates from Sorted Array
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.