Category: sort

Merge Sort Template

public void sortIntegers2(int[] A) {
    // use a shared temp array, the extra memory is O(n) at least
    int[] temp = new int[A.length];
    mergeSort(A, 0, A.length - 1, temp);
}
private void mergeSort(int[] A, int start, int end, int temp){
    if(start >= end){
        return;
    }
    int mid = start + (end - start) / 2;
    mergeSort(A, start, mid, temp);
    mergeSort(A, mid + 1, end, temp);
    merge(A, start, mid, end, temp);
}
private void merge(int[] A, int start, int mid, int end, int[] temp){
    int left = start;
    int right = mid + 1;
    int index = start;
    // merge two sorted subarrays in A to temp array
    while(left <= mid && right <= end){
        if(A[left] < A[right]){
            temp[index++] = A[left++];
        } else {
            temp[index++] = A[right++];
        }
    }
    while(left <= mid){
        temp[index++] = A[left++];
    }
    while(right <= mid){
        temp[index++] = A[right++];
    }
    // copy temp back to A
    for(index = start; index <= end; index++){
        A[index] = temp[index];
    }
}
Advertisements

High Five

/**
 * @param results a list of <student_id, score>
 * @return find the average of 5 highest scores for each person
 * Map<Integer, Double> (student_id, average_score)
 */
public Map<Integer, Double> highFive(Record[] results) {
    Map<Integer, Double> answer = new HashMap<>();
    Map<Integer, List<Integer>> hash = new HashMap<Integer, List<Integer>>();
    for(Record r : results){
        if(!hash.containsKey(r.id)){
            hash.put(r.id, new ArrayList<Integer>());
        }
        if(hash.get(r.id).size() < 5){
            hash.get(r.id).add(r.score);
        } else {
            int lowest_index = 0;
            for(int i = 1; i < 5; i++){
                if(hash.get(r.id).get(i) < hash.get(r.id).get(lowest_index)){
                    lowest_index = i;
                }
            }
            if(hash.get(r.id).get(lowest_index) < r.score){
                hash.get(r.id).set(lowest_index, r.score);
            }
        }
    }
    for(Map.Entry<Integer, List<Integer>> entry : hash.entrySet()){
        int id = entry.getKey();
        List<Integer> scores = entry.getValue();
        double average = 0.0;
        for(int i = 0; i < scores.size(); i++){
            average += scores.get(i);
        }
        average /= scores.size();
        answer.put(id, average);
    }
    return answer;
}

K Closest Points

/**
 * @param points a list of points
 * @param origin a point
 * @param k an integer
 * @return the k closest points
 */
public Point[] kClosest(Point[] points, Point origin, int k) {
    final Point global_origin = origin;
    PriorityQueue<Point> priorityqueue = new PriorityQueue<Point>(k, new Comparator<Point>(){
            @Override
            public int compare(Point a, Point b){
                int diff = getDistance(b, global_origin) - getDistance(a, global_origin);
                if(diff == 0){
                    diff = b.x - a.x;
                }
                if(diff == 0){
                    diff = b.y - a.y;
                }
                return diff;
            }
        });
    
    for(int i = 0; i < points.length; i++){
        priorityqueue.offer(points[i]);
        if(priorityqueue.size() > k){
            priorityqueue.poll();
        }
    }
    k = priorityqueue.size();
    Point[] res = new Point[k];
    while(!priorityqueue.isEmpty()){
        res[--k] = priorityqueue.poll();
    }
    return res;
}
private int getDistance(Point a, Point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

sort map by value

Class ValueComparator implements Comparator<String> {
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    public ValueComparator(HashMap<String, Integer> map){
        this.map.putAll(map);
    }
    int compare(String key1, String key2){
        if(map.get(key1) < map.get(key2)){
            return 1;
        } else {
            return -1;
        }
    }
}
...
Comparator<String> comparator = new ValueComparator(originalMap);
TreeMap<String, Integer> result = new TreeMap<String, Integer>(comparator);
result.putAll(orignalMap);
return result;

java-sort-map-by-value

Top K Frequent Elements

/*Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2]
*/
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k){
    //count the frequency for each element
    HashMap<Integer, Integer> map = new HashMap<>();
    for(int n : nums){
        if(map.containsKey(n)){
            int temp = map.get(n);
            map.put(n, temp + 1);
        } else {
            map.put(n, 1);
        }
    }
    // create a min heap
    PriorityQueue<Pair> queue = new PriorityQueue<>(new Comparator<Pair>(){
        public int compare(Pair a, Pair b){
            return a.count - b.count;
        }
    });
    //maintain a heap of size k
    for(Map.Entry<Integer, Integer> entry : map.entrySet()){
        Pair temp = new Pair(entry.getKey(), entry.getValue());
        queue.offer(temp);
        if(queue.size() > k){
            queue.poll();
        }
    }
    //get all elements from the heap
    List<Integer> res = new ArrayList<>();
    while(!queue.isEmpty()){
        Pair temp = queue.poll();
        res.add(temp.num);
    }
    Collections.reverse(res);
    return res;
}   
}
class Pair {
    int num;
    int count;
    Pair(int num, int count){
        this.num = num;
        this.count = count;
    }
}

Reference:top-k-frequent-elements

Quick Sort template


public void sortIntegers(int[] A) {
	quicksort(A, 0, A.length - 1);
}

private void quicksort(int[] array, int start, int end){
	if(start >= end){
		return;
	}
	int index = partition(array, start, end);
	quicksort(array, start, index - 1);
	quicksort(array, index + 1, end);
}

private int partition(int[] array, int start, int end){
	int pivot = array[end];
	int i = start - 1;
	for(int j = start; j < end; j++){
		if(array[j] <= pivot){
			swap(array, ++i, j);
		}
	}
	swap(array, i + 1, end);
	return i + 1;
}

private void swap(int [] array, int i, int j){
	int temp;
	temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}