FindAllDuplicatesInAnArray [source code]

public class FindAllDuplicatesInAnArray {
static
/******************************************************************************/
public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            nums[nums[i] % (n + 1) - 1] += n + 1;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] / (n + 1) == 2)
                res.add(i + 1);
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FindAllDuplicatesInAnArray.Solution tester = new FindAllDuplicatesInAnArray.Solution();
        int[][] inputs = {
            {4,3,2,7,8,2,3,1}, {2,3},
            {}, {},
            {1,2,2,3,3,3,4,4,4,4}, {2},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] nums = inputs[2 * i];
            String input = Printer.array(nums);
            String expected = Printer.array(inputs[1 + 2 * i]);
            System.out.println(Printer.seperator());
            String output = Printer.array(tester.findDuplicates(nums).toArray(new Integer[0]));
            System.out.println(Printer.wrapColor(input, "magenta") + " -> " + output + Printer.wrapColor(", expected: " + expected, output.equals(expected) ? "green" : "red"));
        }
    }
}

又是一个O(1) space的要求, 回想一下这种问题一般的思路总结有:

• bit manipulation
• pattern题
• In place (use input to store)
• recursion

其中InPlace这一条比较复杂, 因为很多时候涉及到input array本身的修改, 然而这个修改的方式也是完全没有规定的套路的; 任何你在其他的array问题里面碰到过的操作, 这里都可能出现;

这里思考了半天, 好像最后只能依靠于InPlace来做了. 不是说这个是最后的希望, 而是往往在大部分这样的问题里面, InPlace modification往往是一个万金油的方案, 只不过有时候这个modification的方法本身并不是那么好想到, 所以一开始往往尽量避免往这个方向上面想.

这个题目好像之前DisappearedNumber的时候碰到过一个可以解决这个问题的算法; 这个题目触发InPlace思路的还有一个导火索是, 这里给了所有的entry的domain, 很有特点, 跟index的domain是相同的. 同时联想这个问题的传统办法: 历史信息流, more specifically, counts flag类的问题; 这里一个诱导性的思路就是让你直接用原来的input array作为hash/flag array;

想到思路之后就是做了. 那个DisappearedNumber的问题里面, 最后的方法是每一个出现的数字都修改自己的value对应index位置上面的数值, 修改方法是取相反数; 这里用取相反数不行: 这一题跟那一题的一个区别在于, 那一题要找出出现奇数次的数字, 而这一题要找出的是出现偶数次的数字. 如果还用binary的相反数操作, 那么就无法区别出现2次的和出现0次的. 这里就要找另外一种处理办法;

一个办法就是这里采用的取模操作;

另外写main的时候的一个小插曲:

String output = Printer.array(tester.findDuplicates(nums).toArray(new Integer[0]));

这里的这个Integer不能换成int, 因为好像这里这个type实际上是一个泛型参数, 所以不能是primitive;

注意index和entry之间的+1/-1的转换; 这个是这种类hash问题当中通用的一个需要警惕的地方了;

这里的base用n不行, 要用n+1; 主要也是因为value比index大1, 所以value实际可以取到的最大值是n, 而不是n-1;

最后的速度是16(80), 还可以接受;

另外, 当你核心算法写出来之后, 一定要记得检查一下是否需要Corner Case, 比如Empty input, 尤其是看看, 比如你有没有hardcode进去的array acess(nums[0] is illegal if nums.length is smaller than 1). 不过这个问题检查了一下可以看到实际上是没有必要特别处理Empty case的;

discussion上面看到一个更好的做法:

public class Solution {  
    // when find a number i, flip the number at position i-1 to negative.   
    // if the number at position i-1 is already negative, i is the number that occurs twice.  

    public List<Integer> findDuplicates(int[] nums) {  
        List<Integer> res = new ArrayList<>();  
        for (int i = 0; i < nums.length; ++i) {  
            int index = Math.abs(nums[i])-1;  
            if (nums[index] < 0)  
                res.add(index+1);  
            nums[index] = -nums[index];  
        }  
        return res;  
    }  
}

这个整体的思路是类似的, 还是用一个hashing的思路; 区别在于他这里只用1个pass就完成了: 我的思路是走完一个pass之后收集所有的可用信息, 然后分析. 他这里则是, 只记录第一次occurrence. 这样当后面出现第二次occurrence之后, 自动就能够发现duplicate(同是second occurrence本身并不造成任何的修改). 这个就很聪明;

其实像这种value domain equals index domain的array题目, 也算作是一个特别的类型了, 是特别容易诱导到hashing的做法上面去的;

另外, 如果是真是的interview, 可能会被问到, 你这个做法修改了input, 那么能否recover? 这个其实是很简单的, 直接找到所有的负数然后reverse就行了;

说起来, 我的算法也是可以recover的, 直接一个mod就行了;

不过突然想到, 这种用InPlace modification完成的O(1) space算法其实是比较无聊的, 因为实际问题当中, 你直接修改了input, 是很有可能在多线程的场合下造成错误的;

discussion里面有一个人也是一个类似的算法, 但是声称"without destroying the input array", 事实上recover跟without destroying/modifying是两回事的;

我的算法比他们的这个相反数的算法要慢, 主要还是因为division和mod的速度还是不能忽略的; 不过另一个方面来考虑, 我感觉我的算法比他们的算法更general: 我的算法其实可以找到the elements that occured exactly i times for any i. 试验了一下, 确实是可以的.

public class Solution {  
    public List<Integer> findDuplicates(int[] nums) {  
        List<Integer> res=  new ArrayList<>();  
        if(nums == null || nums.length == 0) return res;  
        int i = 0;  
        int n = nums.length;  
        while(i<n){ //traverse the array  till the end  
            if(nums[i] == i+1){  // if number stays at it's supposed position, just continue  
                i++;  
                continue;  
            }  
            int num = nums[i];  
            if(num == -1){ // if the duplicate number in that position is already found continue  
                i++;  
                continue;  
            }  
            if(nums[num-1] == num){ // if current  num is equals to the number at supposed position,  
                res.add(num);       // then it is duplicate.  
                nums[i] = -1;       // mark this position, in order to denote that duplicate has found  
                i++;  
                continue;  
            }  
            swap(nums, i, num-1);  // if current numbers supposed position is occupied by another number swap and consider that number  
        }  
        return res;  
    }  

    public void swap(int nums[], int i ,int j){  
        int tmp = nums[i];  
        nums[i] = nums[j];  
        nums[j] = tmp;  
    }  
}

这个是discussion上面另外一个比较基础的做法. 这个做法就是一个很基本功的做法, 实际最后也是能够达到同样的效果的.

这个算法贴出来还有一个目的, 就是还是重申一下以前的一个观点, array问题其实跟LinkedList类的问题有点像, 很多时候只要你主动往常见的subroutine上面去靠, 往往就能靠出来一个答案. 这题这个用swap的答案并不是一个最好的答案, 但是始终是能够在这个思路上面做出来一个答案的;

另外这里的swap的思路其实是更直观的类似counting sort, 只不过这个题目因为domain非常特殊, 所以counting sort的reordering就显得非常的简单.

我这个思路好像在discussion居然还是有其他人也是这么写的;

另外这个是discussion上面一个人给所有解法的一个总结:

1. the first one is recording if a number is presented in the array or not. Taking advantage of the problem input constraint, there are only positive integers. When a number is inverted at bit-level, we can tell the original number as well as if the number is inverted. Some other reversible operations can be used as well: simple negation, or add the array size. I like bitwise inverse because it is the simplest one in terms of implementation effort and hardware complexity. Oh, and inverse has the highest flexibility: negation only covers "positive" integers" instead of "non-negative" ones, and size offest needs to handle overflow issue carefully.
2. Swap-based approach is to put number 'x' into position 'x-1'. When there is a collision, then we know the number is repeated. (I like to make my thinking clean and I make the position shift outside the loop (see declaration of 'int* arr'), so you won't see that coming in the loop body. )

其实他这个bit inverse的做法, 也就是 ~ , 跟取相反数本质上是差不多的; 不过这个人的总结还是不错的; 我这种方法确实要考虑overflow怎么处理;

Problem Description

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]
Difficulty:Medium
Total Accepted:31.9K
Total Submissions:57.8K
Contributor: shen5630
Companies
pocket gems
Related Topics
array
Similar Questions
Find All Numbers Disappeared in an Array