@@ -0,0 +1,2009 @@
+package array;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.List;%0A%0Apublic class FindAllNumbersDisappearedInAnArray %7B%0A%0A    //TAG: Google%0A    //TAG: array%0A    //Difficulty: Easy%0A%0A    /**%0A     * 448. Find All Numbers Disappeared in an Array%0A     * Given an array of integers where 1 %E2%89%A4 a%5Bi%5D %E2%89%A4 n (n = size of array), some elements appear twice and others appear once.%0A%0A     Find all the elements of %5B1, n%5D inclusive that do not appear in this array.%0A%0A     Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.%0A%0A     Example:%0A%0A     Input:%0A     %5B4,3,2,7,8,2,3,1%5D%0A%0A     Output:%0A     %5B5,6%5D%0A     */%0A%0A    /**%0A     * Solution: From leetcode%0A     * Mark numbers at it's proper location (may not be the same number) to neg number to mark it as found%0A     * *** e.g. when found 2, mark the num%5B1%5D as neg number which num%5B1%5D may not equals to 2, but just mark as neg ***%0A     * then loop second time, when any number is not neg number, e.g. num%5B5%5D %3E 0 means 6 is not set and found, add%0A     * it to list%0A     *%0A     * Time: O(2n) = O(n)%0A     * Space: O(1)%0A     */%0A%0A    public List%3CInteger%3E findDisappearedNumbers(int%5B%5D nums) %7B%0A        List%3CInteger%3E list = new ArrayList%3C%3E();%0A        if (nums == null %7C%7C nums.length == 0) return list;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            /*%0A            Mark each number at it proper location, e.g. 1 should be at index 0, and mark it negative number%0A            to mark it as found%0A             */%0A            int index = Math.abs(nums%5Bi%5D) - 1;%0A            if (nums%5Bindex%5D %3E 0) nums%5Bindex%5D = -nums%5Bindex%5D;%0A        %7D%0A        //Loop array again, if any number is not negative, means it's not set, and i + 1 is the missing number%0A        /*%0A        Be aware the number at number%5Bi%5D is not i - 1 itself, but mark it neg number to represent found i - 1 number%0A         */%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            if (nums%5Bi%5D %3E 0) list.add(i + 1);%0A        %7D%0A        return list;%0A    %7D%0A%0A%7D%0A

448. Find All Numbers Disappeared in an Array