Given 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:
Question
Given 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:
Solution
The problem is asking to return an array of all the integers that appear twice in the given array. The given array has a length of n and all the integers are in the range [1, n]. Each integer appears once or twice. The algorithm should run in O(n) time and use only constant extra space.
Here is a Python solution using the idea of marking the visited numbers:
def findDuplicates(nums):
res = []
for x in nums:
if nums[abs(x)-1] < 0:
res.append(abs(x))
else:
nums[abs(x)-1] *= -1
return res
This solution works by iterating over the input list and for each number, it flips the sign of the number at the corresponding index in the list (1-indexed). If we encounter a number that is already negative, it means we have seen this number before, so we add it to the result list.
For example, if we have the list [4,3,2,7,8,2,3,1], the first number is 4, we go to the 4th index and flip the sign of the number there. We continue this process for all numbers. When we encounter a number that is already negative, it means we have seen this number before, so we add it to the result list.
This solution runs in O(n) time as it makes a single pass over the list, and it uses O(1) extra space as it only uses a constant amount of space to store the result list and the current number.
Similar Questions
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.
Given an array of integers A, every element appears twice except for one. Find that single one.NOTE: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?Problem Constraints1 <= |A| <= 20000000 <= A[i] <= INTMAXInput FormatFirst and only argument of input contains an integer array A.Output FormatReturn a single integer denoting the single element.Example InputInput 1: A = [1, 2, 2, 3, 1]Input 2: A = [1, 2, 2]Example OutputOutput 1: 3Output 2: 1Example ExplanationExplanation 1:3 occurs once.Explanation 2:1 occurs once.
You are given an array nums, where each number in the array appears either once or twice.Return the bitwise XOR of all the numbers that appear twice in the array, or 0 if no number appears twice. Example 1:Input: nums = [1,2,1,3]Output: 1Explanation:The only number that appears twice in nums is 1.Example 2:Input: nums = [1,2,3]Output: 0Explanation:No number appears twice in nums.Example 3:Input: nums = [1,2,2,1]Output: 3Explanation:Numbers 1 and 2 appeared twice. 1 XOR 2 == 3. Constraints:1 <= nums.length <= 501 <= nums[i] <= 50Each number in nums appears either once or twice.
You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.You are given an integer array nums representing the data status of this set after the error.Find the number that occurs twice and the number that is missing and return them in the form of an array. Example 1:Input: nums = [1,2,2,4]Output: [2,3]
Given an array of integers, every element appears thrice except for one, which occurs once. Find that element that does not appear thrice. NOTE: Your algorithm should have a linear runtime complexity. Can you implement it without using extra memory?Problem Constraints2 <= A <= 5*1060 <= A <= INTMAXInput FormatFirst and only argument of input contains an integer array A.Output FormatReturn a single integer.Example InputInput 1: A = [1, 2, 4, 3, 3, 2, 2, 3, 1, 1]Input 2: A = [0, 0, 0, 1]Example OutputOutput 1: 4Output 2: 1Example ExplanationExplanation 1: 4 occurs exactly once in Input 1. 1 occurs exactly once in Input 2.
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.