leetcode 448 Find All Numbers Disappeared in an Ar

MoAir 發(fā)布于2019-08-15 13:54 / 2611人閱讀

摘要：如果這個(gè)位置的值為正意味著我們還沒(méi)有對(duì)這個(gè)元素進(jìn)行過(guò)操作，我們將這個(gè)位置的元素的值取負(fù)。在整個(gè)遍歷結(jié)束后，沒(méi)有取負(fù)的值的索引，就可以對(duì)應(yīng)到?jīng)]有在數(shù)組出現(xiàn)過(guò)的值解法

題目詳情

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.題目要求，輸入一個(gè)大小為n的數(shù)組，數(shù)組中包含著值為1～n的元素，有的值出現(xiàn)過(guò)一次，有的值出現(xiàn)過(guò)兩次，而我們需要找到?jīng)]有在數(shù)組中出現(xiàn)的1～n中的值，并以L(fǎng)ist形式返回這些值。
這道題額外要求了我們需要在O(n)的時(shí)間復(fù)雜度下解決這個(gè)問(wèn)題，同時(shí)不使用額外空間（返回的list不算做額外空間）
Example:
Input:[4,3,2,7,8,2,3,1]   
Output:[5,6]

思路

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

如果這個(gè)位置的值為正（意味著我們還沒(méi)有對(duì)這個(gè)元素進(jìn)行過(guò)操作），我們將這個(gè)位置的元素的值取負(fù)。

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

解法

    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;   
    }