442. Find All Duplicates in an Array
in Array an Find all Duplicates
2023-09-11 14:22:44 时间
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
Input: [4,3,2,7,8,2,3,1] Output: [2,3]
Approach #1: Math. [Java]
class Solution { public List<Integer> findDuplicates(int[] nums) { List<Integer> ans = new ArrayList<>(); for (int i = 0; i < nums.length; ++i) { int index = Math.abs(nums[i]) - 1; if (nums[index] < 0) ans.add(Math.abs(index+1)); nums[index] = -nums[index]; } return ans; } }
Analysis:
When find a number i flip the number to negtive at position i-1,
If the number at position i-1 is already negative, i is the occurs twice.
Reference:
https://leetcode.com/problems/find-all-duplicates-in-an-array/discuss/92387/Java-Simple-Solution
相关文章
- Leetcode: Find All Numbers Disappeared in an Array
- Leetcode: Find All Duplicates in an Array
- Leetcode: Maximum XOR of Two Numbers in an Array
- Leetcode: Kth Largest Element in an Array
- Leetcode: Find Minimum in Rotated Sorted Array II
- Leetcode: Find Minimum in Rotated Sorted Array
- App.Config Transformation for projects which are not Web Projects in Visual Studio? app.debug.config
- Action Results in Web API 2
- 【LeetCode-面试算法经典-Java实现】【033-Search in Rotated Sorted Array(在旋转数组中搜索)】
- 关于微信小程序报错:Some selectors are not allowed in component wxss, including tag name selectors...
- C#,数值计算(Numerical Recipes in C#),稀疏矩阵的相乘(ADAT)算法与源代码
- [geeksforgeeks] Count the number of occurrences in a sorted array
- jediscluster运行过程中出现no reachable node in cluster异常
- 浅析Array新特性flat()与flatMap()、为什么引入flatMap及array.flatMap()的工作原理
- vue These dependencies were not found: * core-js/modules/es.array.iterator in ./node_modules/@babe
- LeetCode Search in Rotated Sorted Array 在旋转了的数组中查找
- [置顶] think in java interview-高级开发人员面试宝典代码示例
- npm报错:A complete log of this run can be fund in:解决方案
- [LeetCode] 961. N-Repeated Element in Size 2N Array 在大小为2N的数组中重复N次的数字
- [LeetCode] Find All Duplicates in an Array 找出数组中所有重复项
- [LeetCode] 421. Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字
- [LeetCode] 215. Kth Largest Element in an Array 数组中第k大的数字
- How to Check if an Array Contains a Value in Java Efficiently?---reference
- 215. Kth Largest Element in an Array
- 153. Find Minimum in Rotated Sorted Array