Contains Duplicate

​​https://leetcode.com/problems/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.

方法一，想到的简单方法

int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}

bool containsDuplicate(int* nums, int numsSize) {
   int i;

   // 
   qsort(nums, numsSize, sizeof(nums[0]), cmp);

   for(i = 1; i < numsSize; ++i) {
        if(nums[i] == nums[i-1])
            return true;
   }

    return  false;
}

方法二，基于插入排序改进，效率更高

bool containsDuplicate(int* nums, int numsSize) {
   int i, j, key;

   for(i = 1; i < numsSize; ++i) {

       j = i -1;
       key = nums[i];
       while(j > 0 && nums[j] > key) {
           nums[j + 1] = nums[j];   // move to back
           j--;
       }

       if(j != (i-1))
        nums[j + 1] = key;

        if(nums[j] == key)
            return true;
   }

    return  false;
}