Welcome to Subscribe On Youtube
-
import java.util.ArrayList; import java.util.List; /** Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space. Example: Input: [4,3,2,7,8,2,3,1] Output: [5,6] */ public class Find_All_Numbers_Disappeared_in_an_Array { public static void main(String[] args) { Find_All_Numbers_Disappeared_in_an_Array out = new Find_All_Numbers_Disappeared_in_an_Array(); Solution s = out.new Solution(); int[] a = new int[]{4,3,2,7,8,2,3,1}; System.out.println(s.findDisappearedNumbers(a)); } class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { // put value to its index position, value x should be at index x-1 // key is to handle duplicate int i = 0; int missingCount = 0; while (i < nums.length) { if (nums[i] > nums.length) { i++; } else if (nums[i] != i + 1) { // check duplicate if (nums[nums[i] - 1] == nums[i]) { // find dup nums[i] = nums.length + 1; // @key: mark outlier //@key: better mark it as negative, to avoid wrong answer missingCount++; } else { // switch int tmp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = tmp; } } else if (nums[i] == i + 1) { i++; } } List<Integer> result = new ArrayList<>(); for (int j = 0; j < nums.length; j++) { if (nums[j] > nums.length) { result.add(j + 1); } } return result; } } } ############ class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { int n = nums.length; for (int i = 0; i < n; ++i) { int idx = Math.abs(nums[i]) - 1; if (nums[idx] > 0) { nums[idx] *= -1; } } List<Integer> res = new ArrayList<>(); for (int i = 0; i < n; ++i) { if (nums[i] > 0) { res.add(i + 1); } } return res; } } -
// OJ: https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/ // Time: O(N) // Space: O(1) class Solution { public: vector<int> findDisappearedNumbers(vector<int>& A) { int N = A.size(); for (int i = 0; i < N; ++i) { while (A[A[i] - 1] != A[i]) swap(A[A[i] - 1], A[i]); } vector<int> ans; for (int i = 0; i < N; ++i) { if (A[i] != i + 1) ans.push_back(i + 1); } return ans; } }; -
class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: for num in nums: idx = abs(num) - 1 if nums[idx] > 0: nums[idx] *= -1 return [i + 1 for i, v in enumerate(nums) if v > 0] ############ class Solution(object): def findDisappearedNumbers(self, nums): """ :type nums: List[int] :rtype: List[int] """ ans = [] for i in range(0, len(nums)): idx = abs(nums[i]) - 1 nums[idx] = -nums[idx] if nums[idx] > 0 else nums[idx] for i in range(0, len(nums)): if nums[i] > 0: ans.append(i + 1) for i in range(0, len(nums)): nums[idx] = -nums[idx] if nums[idx] < 0 else nums[idx] return ans -
func findDisappearedNumbers(nums []int) []int { for _, num := range nums { idx := abs(num) - 1 if nums[idx] > 0 { nums[idx] *= -1 } } var res []int for i, num := range nums { if num > 0 { res = append(res, i+1) } } return res } func abs(a int) int { if a > 0 { return a } return -a } -
function findDisappearedNumbers(nums: number[]): number[] { for (let i = 0; i < nums.length; i++) { let idx = Math.abs(nums[i]) - 1; if (nums[idx] > 0) { nums[idx] *= -1; } } let ans = []; for (let i = 0; i < nums.length; i++) { if (nums[i] > 0) { ans.push(i + 1); } } return ans; }
-
class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { int length = nums.length; for (int i = 0; i < length; i++) { while (nums[i] != i + 1) { if (nums[i] == nums[nums[i] - 1]) break; int temp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = temp; } } List<Integer> disappearedNumbers = new ArrayList<Integer>(); for (int i = 0; i < length; i++) { if (nums[i] != i + 1) disappearedNumbers.add(i + 1); } return disappearedNumbers; } } ############ class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { int n = nums.length; for (int i = 0; i < n; ++i) { int idx = Math.abs(nums[i]) - 1; if (nums[idx] > 0) { nums[idx] *= -1; } } List<Integer> res = new ArrayList<>(); for (int i = 0; i < n; ++i) { if (nums[i] > 0) { res.add(i + 1); } } return res; } } -
// OJ: https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/ // Time: O(N) // Space: O(1) class Solution { public: vector<int> findDisappearedNumbers(vector<int>& A) { int N = A.size(); for (int i = 0; i < N; ++i) { while (A[A[i] - 1] != A[i]) swap(A[A[i] - 1], A[i]); } vector<int> ans; for (int i = 0; i < N; ++i) { if (A[i] != i + 1) ans.push_back(i + 1); } return ans; } }; -
class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: for num in nums: idx = abs(num) - 1 if nums[idx] > 0: nums[idx] *= -1 return [i + 1 for i, v in enumerate(nums) if v > 0] ############ class Solution(object): def findDisappearedNumbers(self, nums): """ :type nums: List[int] :rtype: List[int] """ ans = [] for i in range(0, len(nums)): idx = abs(nums[i]) - 1 nums[idx] = -nums[idx] if nums[idx] > 0 else nums[idx] for i in range(0, len(nums)): if nums[i] > 0: ans.append(i + 1) for i in range(0, len(nums)): nums[idx] = -nums[idx] if nums[idx] < 0 else nums[idx] return ans -
func findDisappearedNumbers(nums []int) []int { for _, num := range nums { idx := abs(num) - 1 if nums[idx] > 0 { nums[idx] *= -1 } } var res []int for i, num := range nums { if num > 0 { res = append(res, i+1) } } return res } func abs(a int) int { if a > 0 { return a } return -a } -
function findDisappearedNumbers(nums: number[]): number[] { for (let i = 0; i < nums.length; i++) { let idx = Math.abs(nums[i]) - 1; if (nums[idx] > 0) { nums[idx] *= -1; } } let ans = []; for (let i = 0; i < nums.length; i++) { if (nums[i] > 0) { ans.push(i + 1); } } return ans; }