448. Find All Numbers Disappeared in an Array

DevWiki 發布于2019-08-14 17:28 / 3059人閱讀

摘要：題目鏈接一般這種類型的題要，要么給賦值成不在范圍內的數，要么到對應位置。

448. Find All Numbers Disappeared in an Array

題目鏈接：https://leetcode.com/problems...

一般這種類型的題要in place，要么給num[i]賦值成不在范圍內的數，要么swap到對應位置。

public class Solution {
    public List findDisappearedNumbers(int[] nums) {
        List result = new ArrayList();
        if(nums.length == 0) return result;
        // sign as negative when find a number
        for(int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            nums[index] = -Math.abs(nums[index]);
        }
        // find positive number, whose index is not visited
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) result.add(i + 1);
        }
        return result;
    }
}

swap的方法見discussion:
https://discuss.leetcode.com/...

public class Solution {
    public List findDisappearedNumbers(int[] nums) {
        List result = new ArrayList();
        if(nums.length == 0) return result;
        // swap to correct position
        for(int i = 0; i < nums.length; i++) {
            while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        // find positive number, whose index is not visited
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != i + 1) result.add(i + 1);
        }
        return result;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

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

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

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

[LeetCode] 448. Find All Numbers Disappeared in an

Problem 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...

X_AirDu 2019-08-16 14:28 評論0 收藏0
[LeetCode] 448. Find All Numbers Disappeared in an

Problem 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...

Scorpion 2019-08-16 13:39 評論0 收藏0
leetcode 448 Find All Numbers Disappeared in an Ar

摘要：如果這個位置的值為正意味著我們還沒有對這個元素進行過操作，我們將這個位置的元素的值取負。在整個遍歷結束后，沒有取負的值的索引，就可以對應到沒有在數組出現過的值解法題目詳情 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others ap...

MoAir 2019-08-15 13:54 評論0 收藏0
leetcode448. Find All Numbers Disappeared in an Ar

摘要：題目要求假設一個長度為的整數數組，數組中的元素的值位于區間中。代碼如下但是這個實現違背了的空間復雜度這里結果集不視為額外空間。如果當前元素無需進行交換，則指針右移一位。無需進行的場景是指當前元素已經出現在目標位置上了。題目要求 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some element...

blankyao 2019-08-16 17:09 評論0 收藏0
leedcode 數組：448. Find All Numbers Disappeared in a

摘要：題目描述思路先把數組進行升序排序，再進行數組去重，最后循環比較取得結果。升序排序可以使用若要降序排列可以則是數組去重，我使用的中的方法去重，可以參照一行代碼實現數組去重數組去重數組去重方法最優解源碼排序去重題目描述 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appe...

zero 2019-08-21 15:01 評論0 收藏0