2016年2月2日 星期二

LEET code -- Contains Duplicate

 Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.


Subscribe to see which companies asked this question


我原本是用quick sort直接排序在找有沒有重複
但是這樣會超過時間限制

而且quick的方式pivot很容易選到跟left依樣  所以造成一定回傳true



 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
bool containsDuplicate(int* nums, int numsSize) {
    if(numsSize ==1)return false;
    if(numsSize ==0)return false;
    quicksort(nums,0,numsSize-1);
    for(int i=0;i<numsSize;i++){
        if(nums[i]==nums[i+1])return true;
    }
    return false;
}
int partition(int *nums,int left,int right,int pivotIndex){
    int pivot = nums[pivotIndex];
    int Big=left;
    for(int i=left;i<right;i++){
        if( nums[i] <= pivot ){
            swap(nums,i,Big);
            Big++;
        }
    }
    swap(nums,Big,right);
    return Big;
}

void swap(int *nums,int source, int target){
    nums[source] = nums[source]^nums[target];
    nums[target] = nums[source]^nums[target];
    nums[source] = nums[source]^nums[target];
}

void quicksort(int *nums, int left, int right){
    if(left>=right)return;
        int pivotIndex = partition(nums,left,right,(right+left)/2);
        quicksort(nums,left,pivotIndex-1);
        quicksort(nums,pivotIndex,right);

}

---------
用selected sort
並檢查每次有沒有掃到依樣的


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool containsDuplicate(int* nums, int numsSize) {
    if(numsSize ==1)return false;
    if(numsSize ==0)return false;
    
    for(int i=0;i<numsSize-1;i++){
        int min=nums[i],index=i;
        for(int j=i+1;j<numsSize;j++){
            if(nums[i]==nums[j])return true;
            if(nums[j] < min){
                min=nums[j];
                index=j;
            }
        }
        swap(nums,i,index);
    }
    return false;
}
void swap(int *nums,int source, int target){
    nums[source] = nums[source]^nums[target];
    nums[target] = nums[source]^nums[target];
    nums[source] = nums[source]^nums[target];
}

------------
用內建quick sort
因為內建的pviot選的方式是亂數 會比我的好



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int com(const void *s1, const void *s2){
    return *(int *)s1 - *(int *)s2;
}

bool containsDuplicate(int* nums, int numsSize) {
    if(numsSize ==1)return false;
    if(numsSize ==0)return false;
    qsort(nums,numsSize,sizeof(int),com);
    for(int i=0;i<numsSize;i++){
        if (nums[i] == nums[i+1])return true;
    }
    return false;
}
張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)