8000 [LEET-164] add 164 · FitzroyCM/Leetcode@852cc3a · GitHub
[go: up one dir, main page]
Skip to content

Commit 852cc3a

Browse files
fishercoder1534fishercoder1534
committed
[LEET-164] add 164
1 parent 2def68a commit 852cc3a

File tree

3 files changed

+182
-15
lines changed

3 files changed

+182
-15
lines changed

‎leetcode-algorithms/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -199,7 +199,7 @@
199199
|169|[Majority Element](https://leetcode.com/problems/majority-element/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/MajorityElement.java)| O(n)|O(1) | Easy|
200200
|168|[Excel Sheet Column Title](https://leetcode.com/problems/excel-sheet-column-title/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ExcelSheetColumnTitle.java)| O(n)|O(1) | Easy|
201201
|165|[Compare Version Numbers](https://leetcode.com/problems/compare-version-numbers/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/CompareVersionNumbers.java)| O(n)|O(1) | Easy|
202-
|164|[Maximum Gap](https://leetcode.com/problems/maximum-gap/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/MaximumGap.java) | O(?) |O(?) | Hard|
202+
|164|[Maximum Gap](https://leetcode.com/problems/maximum-gap/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/MaximumGap.java) | O(n) |O(n) | Hard|
203203
|163|[Missing Ranges](https://leetcode.com/problems/missing-ranges/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/MissingRanges.java) | O(n) |O(1) | |
204204
|162|[Find Peak Element](https://leetcode.com/problems/find-peak-element/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/FindPeakElement.java) | O(1) |O(logn)/O(n) | Binary Search|
205205
|161|[One Edit Distance](https://leetcode.com/problems/one-edit-distance/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/OneEditDistance.java) | O(n) |O(1) | |

‎leetcode-algorithms/src/main/java/com/stevesun/solutions/MaximumGap.java

Lines changed: 113 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -4,33 +4,132 @@
44

55
/**
66
* Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
7-
8-
Try to solve it in linear time/space.
9-
10-
Return 0 if the array contains less than 2 elements.
11-
12-
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
7+
* <p>
8+
* Try to solve it in linear time/space.
9+
* <p>
10+
* Return 0 if the array contains less than 2 elements.
11+
* <p>
12+
* You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
1313
*/
1414
public class MaximumGap {
15+
//brute force
1516
public int maximumGap(int[] nums) {
16-
if(nums.length < 2) return 0;
17+
if (nums.length < 2) return 0;
1718

1819
Arrays.sort(nums);
1920
int max = Integer.MIN_VALUE;
20-
for(int i = 1; i < nums.length;){
21-
while(i < nums.length && nums[i] == nums[i-1]){
21+
for (int i = 1; i < nums.length; ) {
22+
while (i < nums.length && nums[i] == nums[i - 1]) {
2223
i++;
2324
}
24-
if(i == nums.length) {
25+
if (i == nums.length) {
2526
i--;
26-
max = (nums[i] - nums[i-1] > max) ? nums[i] - nums[i-1] : max;
27+
max = (nums[i] - nums[i - 1] > max) ? nums[i] - nums[i - 1] : max;
2728
break;
28-
}
29-
else max = (nums[i] - nums[i-1] > max) ? nums[i] - nums[i-1] : max;
30-
if(nums[i] != nums[i-1]){
29+
} else max = (nums[i] - nums[i - 1] > max) ? nums[i] - nums[i - 1] : max;
30+
if (nums[i] != nums[i - 1]) {
3131
i++;
3232
}
3333
}
3434
return max;
3535
}
36+
37+
38+
39+
//http://www.programcreek.com/2014/03/leetcode-maximum-gap-java/
40+
class Bucket {
41+
int min = -1;
42+
int max = -1;
43+
44+
public Bucket() {
45+
this.min = -1;
46+
this.max = -1;
47+
}
48+
}
49+
50+
//compute interval and multiply by interval to get the index
51+
public int maximumGap_from_programcreek_1(int[] nums) {
52+
if (nums == null || nums.length < 2) return 0;
53+
54+
int maxNum = nums[0];
55+
int minNum = nums[0];
56+
for (int i = 0; i < nums.length; i++) {
57+
maxNum = Math.max(maxNum, nums[i]);
58+
minNum = Math.min(minNum, nums[i]);
59+
}
60+
61+
//initialize bucket array
62+
Bucket[] buckets = new Bucket[nums.length + 1];
63+
for (int i = 0; i < buckets.length; i++) {
64+
buckets[i] = new Bucket();
65+
}
66+
67+
double interval = (double) nums.length/(maxNum - minNum);
68+
//distribute the array to different buckets
69+
for (int i = 0; i < nums.length; i++) {
70+
int index = (int) ((nums[i] - minNum) * interval);
71+
if (buckets[index].min == -1) {
72+
buckets[index].min = nums[i];
73+
buckets[index].max = nums[i];
74+
} else {
75+
buckets[index].min = Math.min(nums[i], buckets[index].min);
76+
buckets[index].max = Math.max(nums[i], buckets[index].max);
77+
}
78+
}
79+
80+
//scan through the bucket array to find the maximal gap
81+
int result = 0;
82+
int prev = buckets[0].max;
83+
for (int i = 1; i < buckets.length; i++) {
84+
if (buckets[i].min != -1) {
85+
result = Math.max(result, buckets[i].min - prev);
86+
prev = buckets[i].max;
87+
}
88+
}
89+
90+
return result;
91+
}
92+
93+
//compute gap and divide by gap to get the index
94+
public int maximumGap_from_programcreek_2(int[] nums) {
95+
if (nums == null || nums.length < 2) return 0;
96+
97+
int maxNum = nums[0];
98+
int minNum = nums[0];
99+
for (int i = 0; i < nums.length; i++) {
100+
maxNum = Math.max(maxNum, nums[i]);
101+
minNum = Math.min(minNum, nums[i]);
102+
}
103+
104+
//initialize bucket array
105+
Bucket[] buckets = new Bucket[nums.length + 1];
106+
for (int i = 0; i < buckets.length; i++) {
107+
buckets[i] = new Bucket();
108+
}
109+
110+
double gap = (double) (maxNum - minNum)/(nums.length-1);
111+
//distribute the array to different buckets
112+
for (int i = 0; i < nums.length; i++) {
113+
int index = (int) ((nums[i] - minNum)/gap);
114+
if (buckets[index].min == -1) {
115+
buckets[index].min = nums[i];
116+
buckets[index].max = nums[i];
117+
} else {
118+
buckets[index].min = Math.min(nums[i], buckets[index].min);
119+
buckets[index].max = Math.max(nums[i], buckets[index].max);
120+
}
121+
}
122+
123+
//scan through the bucket array to find the maximal gap
124+
int result = 0;
125+
int prev = buckets[0].max;
126+
for (int i = 1; i < buckets.length; i++) {
127+
if (buckets[i].min != -1) {
128+
result = Math.max(result, buckets[i].min - prev);
129+
prev = buckets[i].max;
130+
}
131+
}
132+
133+
return result;
134+
}
36135
}

‎leetcode-algorithms/src/test/java/com/stevesun/MaximumGapTest.java

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.solutions.MaximumGap;
4+
import org.junit.Before;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static junit.framework.Assert.assertEquals;
9+
10+
public class MaximumGapTest {
11+
private static MaximumGap test;
12+
private static int expected;
13+
private static int actual;
14+
private static int[] nums;
15+
16+
@BeforeClass
17+
public static void setup(){
18+
test = new MaximumGap();
19+
}
20+
21+
@Before
22+
public void setupForEachTest(){
23+
expected = 0;
24+
actual = 0;
25+
}
26+
27+
@Test
28+
public void test1(){
29+
nums = new int[]{};
30+
expected = 0;
31+
actual = test.maximumGap(nums);
32+
assertEquals(expected, actual);
33+
34+
actual = test.maximumGap_from_programcreek_1(nums);
35+
assertEquals(expected, actual);
36+
37+
actual = test.maximumGap_from_programcreek_2(nums);
38+
assertEquals(expected, actual);
39+
}
40+
41+
@Test
42+
public void test2(){
43+
nums = new int[]{1,3,6,5};
44+
expected = 2;
45+
actual = test.maximumGap(nums);
46+
assertEquals(expected, actual);
47+
48+
actual = test.maximumGap_from_programcreek_1(nums);
49+
assertEquals(expected, actual);
50+
51+
actual = test.maximumGap_from_programcreek_2(nums);
52+
assertEquals(expected, actual);
53+
}
54+
55+
@Test
56+
public void test3(){
57+
nums = new int[]{1, 100000};
58+
expected = 99999;
59+
actual = test.maximumGap(nums);
60+
assertEquals(expected, actual);
61+
62+
actual = test.maximumGap_from_programcreek_1(nums);
63+
assertEquals(expected, actual);
64+
65+
actual = test.maximumGap_from_programcreek_2(nums);
66+
assertEquals(expected, actual);
67+
}
68+
}

0 commit comments

Comments
 (0)
0