Sort
Different sorting algorithms
- insertion sort
- selection sort
- bubble sort
- shells sort
- merge sort
- quick sort
- heap sort
Examples
Leetcode 56 Merge Intervals
Problem description:
Given a collection of intervals, merge all overlapping intervals.
| Input | Output |
|---|---|
| [1,3],[2,6],[8,10],[15,18] | [1,6],[8,10],[15,18] |
Solution: O(N log N)
Code
Below is the Pseudo code for check and compute for cj:
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
int size = intervals.size();
if(size<2) return intervals;
// sort the intervals
Collections.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval o1, Interval o2){
if(o1.start < o2.start) return -1;
else if(o1.start > o2.start) return 1;
else{
if(o1.end < o2.end) return -1;
else if(o1.end > o2.end) return 1;
else return 0;
}
}
});
Interval a, b;
List<Interval> resList = new ArrayList<>();
int i=0;
a = intervals.get(i++);
while(i < size){
b = intervals.get(i++);
if(a.end < b.start){
resList.add(a);
a = b;
}else{
//merge
a = new Interval(Math.min(a.start, b.start),
Math.max(a.end, b.end));
}
}
resList.add(a);
return resList;
}- Time: O(N log N)
- Space: O(1)
Leetcode 75 Sort Colors
Problem description
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Follow up: can you give a one pass solution?
Solution
Code
//one pass solution
public class Solution {
public void sortColors(int[] nums) {
int N = nums.length;
int s = 0, t = N - 1, i = 0;
int tmp;
while (i <= t) {
if (nums[i] == 0) {
tmp = nums[i];
nums[i++] = nums[s];
nums[s++] = tmp;
} else if (nums[i] == 2) {
tmp = nums[i];
nums[i] = nums[t];
nums[t--] = tmp;
} else {
i++;
}
}
}
}
public class Teisei {
public static void main(String args[]){
System.out.println("Hello world! This is Teisei's blog");
}
}If you like this post or if you use one of the Open Source projects I maintain, say hello by email. There is also my Amazon Wish List. Thank you ♥
Comments