Demo entry 6784847

test

   

Submitted by anonymous on Mar 11, 2019 at 02:40
Language: Java. Code size: 1.0 kB.

public static List<Integer> getTopLogN(List<Integer> originalList) {
    int index = originalList.size() - (int) round(log(originalList.size()) / log(2);
    int left = 0;
    int right = originalList.size() - 1;
    
    while (true) {
        int pivot = (left + right) / 2;
        pivot = partition(originalList, left, right, pivot);
        
        if (index == pivot) break;
        
        else if (index < pivot) right = pivot - 1;
        else left = pivot + 1;
    }

    return originalList.subList(index, originalList.size());
}

private static int partition(List<Integer> list, int left, int right, int pivot) {
    int pivotVal = list.get(pivot);
    swap(list, pivot, right);

    int tmp = left;
    for (int i = left; i < right; i++) {
        if (list.get(i) < pivotVal) swap(list, tmp++, i);
    }

    swap(list, right, tmp);
    return tmp;
}

private static void swap(List<Integer> list, int a, int b) {
    int tmp = array.get(a);
	array.set(a, array.get(b));
	array.set(b, tmp);
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).