gistfile1.java

	Integer randomizedSelect(List<Integer> elements, int k) {
		if(elements.size() == 1) return elements.get(0);

		Integer pivot = elements.get(0);
		List<Integer> smaller = new ArrayList<Integer>();
		for(Integer i : elements) {
			if(i < pivot) smaller.add(i);
		}

		if(k < smaller.size()) return randomizedSelect(smaller, k);

		List<Integer> equal = new ArrayList<Integer>();
		for(Integer i : elements) {
			if(i == pivot) equal.add(i);
		}

		if(k - smaller.size() < equal.size()) return equal.get(0);

		List<Integer> greater = new ArrayList<Integer>();
		for(Integer i : elements) {
			if(i > pivot) greater.add(i);
		}

		return randomizedSelect(greater, k - smaller.size() - equal.size());
	}