Epoch

題目

  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?

題意

  找出 array 中出現過兩次的數字

想法

  這題與 448. Find All Numbers Disappeared in an Array 有點像，那題是要找出沒有出現的數字，我利用相同的方法，找到某數後，將這個數字作為 index，將此 index 的數加上負號，若是下次遇到相同的數字，因為此 index 已是負數，就可以找到重複的數字。

步驟

  1. 找到數字後

      a. 若此 index 的數是正數，則將此 index 加上負號

      b. 若非就將此數紀錄，表示此為重複出現的數字

程式碼

  int* findDuplicates(int* nums, int numsSize, int* returnSize) {
    int i;
    int c=0;
    int *ret = malloc(sizeof(int)*100000);
    for(i=0; i<numsSize; i++){
        if(nums[abs(nums[i])-1]>0)
            nums[abs(nums[i])-1]*=-1;
        else{
            ret[c]=abs(nums[i]);
            c++;
        }
    }
    *returnSize=c;
    return ret;
}