[LeetCode] 442. Find All Duplicates in an Array

liukai90 發布于2019-08-16 14:28 / 1585人閱讀

Problem

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]

Solution

class Solution {
    public List findDuplicates(int[] nums) {
        //use index to record visited: times -1
        List res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = nums[i] > 0 ? nums[i]-1 : -nums[i]-1;
            if (nums[index] < 0) res.add(index+1);
            nums[index] *= -1;
        }
        return res;
    }
}

云服務器 GPU云服務器 array_find FIND_IN_SET in_array() in_array

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73016.html

leetcode442. Find All Duplicates in an Array

摘要：題目要求存在一個整數數組，其中的所有元素都位于之間，其中是數組的長度。有的元素出現了一次，而有的元素出現了兩次。思路一交換為了在的時間內找到所有的出現兩次的數字，其核心要求在于用現有的數組記錄已經訪問過的元素，同時不會丟失尚未訪問過的元素。題目要求 Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some e...

yimo 2019-08-16 18:27 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[LeetCode] 491. Increasing Subsequences

Problem Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 . Example: ...

wupengyu 2019-08-16 13:50 評論0 收藏0
[Leetcode] Contains Duplicate 包含重復

摘要：代碼集合法復雜度時間空間思路同樣使用集合，但這次我們要維護集合的大小不超過，相當于是記錄一個寬度為的窗口中出現過的數字。 Contains Duplicate I Given an array of integers, find if the array contains any duplicates. Your function should return true if any v...

rozbo 2019-08-14 12:28 評論0 收藏0
leetcode217.219.220 contains duplicate

摘要：輸入一個整數數組，查看數組中是否存在重復的值。新的數組中數組的下標為原數組的值，如果遍歷過，則設置為。這里使用了作為實現的數據結構，通過堆的形式對集合中的數據進行存儲，從而我們可以通過某種順序獲得該集合中的所有順序。 217 Contains Duplicate Given an array of integers, find if the array contains any dup...

tulayang 2019-08-16 10:56 評論0 收藏0