国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode 448 Find All Numbers Disappeared in an Ar

MoAir / 2617人閱讀

摘要：如果這個位置的值為正意味著我們還沒有對這個元素進行過操作，我們將這個位置的元素的值取負。在整個遍歷結(jié)束后，沒有取負的值的索引，就可以對應(yīng)到?jīng)]有在數(shù)組出現(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.
題目要求，輸入一個大小為n的數(shù)組，數(shù)組中包含著值為1～n的元素，有的值出現(xiàn)過一次，有的值出現(xiàn)過兩次，而我們需要找到?jīng)]有在數(shù)組中出現(xiàn)的1～n中的值，并以List形式返回這些值。
這道題額外要求了我們需要在O(n)的時間復(fù)雜度下解決這個問題，同時不使用額外空間（返回的list不算做額外空間）


Example:
Input:[4,3,2,7,8,2,3,1]   
Output:[5,6]
思路

在遍歷每一個值的時候，我們都找到這個值按照元素1～n順序排序時應(yīng)該在的位置。

如果這個位置的值為正（意味著我們還沒有對這個元素進行過操作），我們將這個位置的元素的值取負。

在整個遍歷結(jié)束后，沒有取負的值的索引，就可以對應(yīng)到?jīng)]有在數(shù)組出現(xiàn)過的值

解法 
    public List findDisappearedNumbers(int[] nums) {
             List res = new ArrayList();
        
        for(int num : nums){
            int val = Math.abs(num)-1;
            if(nums[val] > 0){
                nums[val] = - nums[val];
            }
        }
        for(int i =0;i 0){
                res.add(i+1);
            }
        }
        return res;   
    }

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

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68386.html

相關(guān)文章

  • leetcode448. Find All Numbers Disappeared in an Ar

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

    blankyao 評論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 評論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 評論0 收藏0

  • 448. Find All Numbers Disappeared in an Array

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

    DevWiki 評論0 收藏0

  • Leetcode PHP題解--D79 448. Find All Numbers…

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

    X1nFLY 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<