Created
June 24, 2018 10:01
-
-
Save PetrGlad/26309a156e94f69bf072588fe7902f6c to your computer and use it in GitHub Desktop.
Ranges
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Random; | |
import java.util.TreeSet; | |
public class MainSr { | |
public static void main(String[] args) { | |
// Run this with assertions enabled | |
assert 1 == countRanges(new int[]{1}); | |
assert 1 == countRanges(new int[]{2, 1}); | |
assert 1 == countRanges(new int[]{3, 2, 1}); | |
assert 3 == countRanges(new int[]{1, 2, 3}); | |
assert 2 == countRanges(new int[]{2, 1, 3}); | |
assert 3 == countRanges(new int[]{2, 1, 3, 5, 4}); | |
assert 4 == countRanges(new int[]{2, 1, 3, 4, 5}); | |
assert 4 == countRanges(new int[]{1, 3, 2, 4, 5}); | |
largeTimings(); | |
} | |
private static void largeTimings() { | |
// Should complete in reasonable time | |
int a[] = new int[100_000]; | |
Random r = new Random(); | |
for (int c = 0; c < 10; c++) { | |
for (int i = 0; i < a.length; i++) | |
a[i] = r.nextInt(1_000_000_000); | |
System.out.println(countRanges(a)); | |
} | |
} | |
public static int countRanges(int[] a) { | |
final TreeSet<Integer> xs = new TreeSet<>(); | |
for (int x : a) | |
xs.add(x); | |
int count = 0; | |
int idx = 0; | |
while (idx < a.length && !xs.isEmpty()) { | |
int x = xs.pollFirst(); | |
while (idx < a.length && x != a[idx]) { | |
xs.remove(a[idx]); | |
idx++; | |
} | |
count++; | |
} | |
assert count > 0; | |
return count; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment