2016年2月2日 星期二

LEET code -- Single Number III

 Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?



我想說用quick sort去跑 再去找哪個沒重複的
但是他quick sort出來是錯的.....

 測資:[1403617094,-490450406,-1756388866,-967931676,1878401007,1878401007,-74743538,1403617094,-1756388866,-74743538,-490450406,-1895772685]

但是我自己測試這個側資可以   網路上不給過....

而且這版本沒有線性



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp(const void* s1, const void* s2){
    return *(int*)s2 - *(int*)s1;
}
int* singleNumber(int* nums, int numsSize, int* returnSize) {
    //if(nums==NULL)return NULL;
    int *ans=(int *)malloc(2*sizeof(int));
    qsort(nums,numsSize,sizeof(int),cmp);
    for(int i=0;i<numsSize;i++){
        printf("%d ",nums[i]);
    }
    int index=0;
    for(int i=0;i<numsSize;){
        if(i==numsSize-1){
            ans[index++]=nums[i];
            ++i;
        }else  if(nums[i]==nums[i+1]){
            i+=2;
        } else{
            ans[index++]=nums[i];
            ++i;
        }
        if (index ==2)break;
    }
    *returnSize=2;
    return ans;
}

---------------
我知道位甚麼上面的quick會錯了
因為那個側資 數值很大  直接用相減會容易overflow
所要改判斷式


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp(const void* s1, const void* s2){
    int c = *(int *)s1;
      int d = *(int *)s2;
      if(c < d) {return -1;}               //傳回 -1 代表 s1 < s2
      else if (c == d) {return 0;}      //傳回   0 代表 s1 = s2
      else return 1;                          //傳回  1 代表 s1>s2
    
}
int* singleNumber(int* nums, int numsSize, int* returnSize) {
    //if(nums==NULL)return NULL;
    int *ans=(int *)malloc(2*sizeof(int));
    qsort(nums,numsSize,sizeof(int),cmp);
    for(int i=0;i<numsSize;i++){
        printf("%d ",nums[i]);
    }
    int index=0;
    for(int i=0;i<numsSize;){
        if(i==numsSize-1){
            ans[index++]=nums[i];
            ++i;
        }else  if(nums[i]==nums[i+1]){
            i+=2;
        } else{
            ans[index++]=nums[i];
            ++i;
        }
        if (index ==2)break;
    }
    *returnSize=2;
    return ans;
}

-------------------
天才解法!!!!
https://leetcode.com/discuss/52369/c-o-n-time-o-1-space-7-line-solution-with-detail-explanation
https://leetcode.com/discuss/68750/why-diff%26-diff-1-can-pick-one-bit-that-is-one

因為所有數列全部XOR起來 X^=every element
最後只會有X=A^B  (A!=B)
因為A跟B不同，所以在X會有一個bit是1
問題就是怎麼找到X裡面出現的1bit位置
笨方法就是用for去找
但是有更快的!!
方法:
X & -X
假設X=01100，那-X=10100
可以發現兩者and起來 會找到右邊第一個出現1bit的位置

或是X=01101   -X=10011

因為-X 會是X的complement+1  造成會有這樣的現象

於是我們可以找到出現1的位置
而這個1 只會屬於A或B其中一個

於是我們把這個1當作是條件再把全部內容作XOR
會得到A或B的某一個數值




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */

int* singleNumber(int* nums, int numsSize, int* returnSize) {
    int *ans=(int *)malloc(2*sizeof(int));
    int allxor=0,ANS1=0,ANS2=0;
    for(int i=0;i<numsSize;i++){
        allxor^=nums[i];
    }
    //after for loop, the allxor will have ANS1 XOR ANS2
    int flag = allxor & -allxor;
    for(int i=0;i<numsSize;i++){
        if(nums[i]&flag)ANS1^=nums[i];
    }
    ANS2=ANS1^allxor;  // becase the ans1 has the anser, 
    ans[0]=ANS1;
    ans[1]=ANS2;
    *returnSize=2;
    return ans;
}



張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)