[LeetCode] 442. Find All Duplicates in an Array

liukai90 發(fā)布于2019-08-16 14:28 / 1594人閱讀

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云服務(wù)器云服務(wù)器 array_find FIND_IN_SET in_array() in_array

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/73016.html

相關(guān)文章

leetcode442. Find All Duplicates in an Array

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

yimo 2019-08-16 18:27 評(píng)論0 收藏0
前端 | 每天一個(gè) LeetCode

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

張漢慶 2019-08-23 13:42 評(píng)論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 評(píng)論0 收藏0
[Leetcode] Contains Duplicate 包含重復(fù)

摘要：代碼集合法復(fù)雜度時(shí)間空間思路同樣使用集合，但這次我們要維護(hù)集合的大小不超過，相當(dāng)于是記錄一個(gè)寬度為的窗口中出現(xiàn)過的數(shù)字。 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 評(píng)論0 收藏0
leetcode217.219.220 contains duplicate

摘要：輸入一個(gè)整數(shù)數(shù)組，查看數(shù)組中是否存在重復(fù)的值。新的數(shù)組中數(shù)組的下標(biāo)為原數(shù)組的值，如果遍歷過，則設(shè)置為。這里使用了作為實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，通過堆的形式對(duì)集合中的數(shù)據(jù)進(jìn)行存儲(chǔ)，從而我們可以通過某種順序獲得該集合中的所有順序。 217 Contains Duplicate Given an array of integers, find if the array contains any dup...

tulayang 2019-08-16 10:56 評(píng)論0 收藏0