leetcode448. Find All Numbers Disappeared in an Ar

blankyao 發(fā)布于2019-08-16 17:09 / 3449人閱讀

摘要：題目要求假設一個長度為的整數數組，數組中的元素的值位于區(qū)間中。代碼如下但是這個實現(xiàn)違背了的空間復雜度這里結果集不視為額外空間。如果當前元素無需進行交換，則指針右移一位。無需進行的場景是指當前元素已經出現(xiàn)在目標位置上了。

題目要求

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]

假設一個長度為n的整數數組，數組中的元素的值位于[1,n]區(qū)間中。問，該數組中有哪些[1,n]區(qū)間中的整數沒有出現(xiàn)？

思路和代碼

首先可以想到用另一個臨時數組來記錄每個元素出現(xiàn)的次數，則出現(xiàn)次數為零次的元素在數組中沒有出現(xiàn)。代碼如下：

    public List findDisappearedNumbers(int[] nums) {
        int[] temp = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            temp[nums[i]]++;
        }
        
        List result = new ArrayList<>();
        for (int i = 1; i < temp.length; i++) {
            if (temp[i] == 0) {
                result.add(i);
            }
        }
        return result;
    }

但是這個實現(xiàn)違背了O(1)的空間復雜度（這里結果集不視為額外空間）。因此如何才能避免使用臨時數組呢？其實我們可以利用原數組中元素相互調換的方式，將其轉化為一個新的有序的數組。即從最左邊開始，每遇到一個元素，就將其防止到元素的目標位置上，如在第0位上遇到元素i，則將位置i-1上的元素和位置0上的元素進行交換，并在此判斷新的元素是否需要交換。如果當前元素無需進行交換，則指針右移一位。無需進行的場景是指當前元素已經出現(xiàn)在目標位置上了。

    public List findDisappearedNumbers(int[] nums) {
        int index = 0;
        while(index < nums.length) {
            if(nums[index] == nums[nums[index]-1]) {
                nums[nums[index]-1] = nums[index];
                index++;
            }else{
                int tmp = nums[index];
                nums[index] = nums[tmp-1];
                nums[tmp-1] = tmp;
            }
        }
        List result = new ArrayList();
        for(int i = 0 ; i < nums.length ; i++) {
            if(nums[i] != i+1) {
                result.add(i+1);
            }
        }
        return result;
    }

GPU云服務器云服務器 FIND_IN_SET Disappeared Numbers Leetcod

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

轉載請注明本文地址：http://systransis.cn/yun/74414.html

leetcode 448 Find All Numbers Disappeared in an Ar

摘要：如果這個位置的值為正意味著我們還沒有對這個元素進行過操作，我們將這個位置的元素的值取負。在整個遍歷結束后，沒有取負的值的索引，就可以對應到沒有在數組出現(xiàn)過的值解法題目詳情 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
[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
448. Find All Numbers Disappeared in an Array

摘要：題目鏈接一般這種類型的題要，要么給賦值成不在范圍內的數，要么到對應位置。 448. Find All Numbers Disappeared in an Array 題目鏈接：https://leetcode.com/problems... 一般這種類型的題要in place，要么給num[i]賦值成不在范圍內的數，要么swap到對應位置。 public class Solution ...

DevWiki 2019-08-14 17:28 評論0 收藏0
Leetcode PHP題解--D79 448. Find All Numbers…

摘要：題目鏈接題目分析給定一個到的數組，返回其中缺失的數字。思路用得出到的數字，再用和給定的數組計算差集。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D79 448. Find All Numbers Disappeared in an Array 題目鏈接 448. Find All Numbers Disappeared in an Array 題目分析給定一個1到n的數組，返回...

X1nFLY 2019-07-01 13:57 評論0 收藏0