LeetCode 217

 1 /*************************************************************************
 2     > File Name: LeetCode217.c
 3     > Author: Juntaran
 4     > Mail: Jacinthmail@gmail.com
 5     > Created Time: Tue 10 May 2016 03:15:05 PM CST
 6  ************************************************************************/
 7  
 8 /*************************************************************************
 9     
10     Contains Duplicate
11     
12     Given an array of integers, find if the array contains any duplicates. 
13     Your function should return true if any value appears at least twice in the array, 
14     and it should return false if every element is distinct.
15     
16  ************************************************************************/
17 
18 #include <stdio.h>
19 
20 void quick_sort( int* nums, int left, int right )
21 {    
22     if( left < right )
23     {
24         int i = left;
25         int j = right;
26         int flag = nums[left];
27         
28         while( i < j )
29         {
30             while( i<j && nums[j]>=flag )    // 从右向左找第一个小于x的数  
31             {
32                 j--;
33             }
34             if( i < j )
35             {
36                 nums[i++] = nums[j];
37             }
38         
39             while( i<j && nums[i]<flag )    // 从左向右找第一个大于等于x的数
40             {
41                 i++;
42             }
43             if( i < j )
44             {
45                 nums[j--] = nums[i];
46             }
47         }  
48         nums[i] = flag;
49         quick_sort( nums, left, i-1 );
50         quick_sort( nums, i+1, right);
51     }
52 }
53 
54 int containsDuplicate( int* nums, int numsSize )
55 {
56     int ret = 0;
57     if( numsSize < 2 )
58     {
59         ret = 0; 
60     }
61     quick_sort( nums, 0, numsSize-1 );
62     printfNums( nums, numsSize );
63     
64     int i;
65     for( i=0; i<numsSize; i++ )
66     {
67         if( nums[i] == nums[i+1] )
68         {
69             ret = 1;
70         }
71     }
72     printf("\n%d\n", ret);
73     return ret;
74 }
75 
76 void printfNums( int* nums, int numsSize )
77 {
78     int i;
79 
80     for( i=0; i<numsSize; i++ )
81     {
82         printf("%d ", nums[i]);
83     }
84 }
85 
86 int main()
87 {
88     int nums[] = { 9,8,7,6,5,4,3,2,1,0 };
89     int numsSize = 10;
90     containsDuplicate( nums, numsSize );    
91     
92     return 0;
93 }