leetcode/src/274.c at master · lennylxx/leetcode · GitHub

Name: leetcode/src/274.c at master · lennylxx/leetcode · GitHub
Rating: 4.7 (4682 reviews)
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<stdio.h>
#include<assert.h>

voidquicksort(int*nums, intstart, intend);

staticinlineintmin(inta, intb) {
return (a<b) ? a : b;
}

inthIndex(int*citations, intcitationsSize) {
if (citations==NULL||citationsSize==0) return0;
quicksort(citations, 0, citationsSize);

inthIndex=0;
inti;
for (i=0; i<citationsSize; i++) {
inth=min(citations[i], citationsSize-i);
if (h>hIndex) hIndex=h;
if (citationsSize-i<citations[i]) {
break;
 }
 }

returnhIndex;
}

voidquicksort(int*nums, intstart, intend) {
if (start >= end) return;

inti=start;
intj=end-1;
intsentinal=nums[start];
while (i<j) {
while (i<j&&nums[j] >= sentinal) j--;
nums[i] =nums[j];
while (i<j&&nums[i] <= sentinal) i++;
nums[j] =nums[i];
 }

nums[i] =sentinal;
quicksort(nums, start, i);
quicksort(nums, i+1, end);
}

inthIndex0(int*citations, intcitationsSize) {
if (citations==NULL||citationsSize==0) return0;
quicksort(citations, 0, citationsSize);

inthIndex=0;
inti;
for (i=citationsSize-1; i >= 0; i--) {
if (citations[i] >hIndex) {
hIndex++;
 }
else {
break;
 }
 }

returnhIndex;
}

intmain() {

intcitations0[] = { 3, 0, 6, 1, 5 };
intcitations1[] = { 0 };
intcitations2[] = { 1 };
intcitations3[] = { 1, 2, 2 };
intcitations4[] = { 2, 2 };

assert(hIndex(citations0, sizeof(citations0) / sizeof(citations0[0])) ==3);
assert(hIndex(citations1, sizeof(citations1) / sizeof(citations1[0])) ==0);
assert(hIndex(citations2, sizeof(citations2) / sizeof(citations2[0])) ==1);
assert(hIndex(citations3, sizeof(citations3) / sizeof(citations3[0])) ==2);
assert(hIndex(citations4, sizeof(citations4) / sizeof(citations4[0])) ==2);

printf("all tests passed!\n");

return0;
}