Java’da K’nıncı En Büyük Elemanı Bulmak

Verilen [3,2,1,5,6,4]  dizisi için k = 2 ise dizideki en büyük ikinci eleman  5 olmalıdır..

Java’da K’nıncı en büyük elemanı bulmak için çeşitli yöntemlere gidilebilir.

Aşağıdaki kodda belirtildiği gibi dizi sıralanıp sondan k önceki eleman alınarak çözüme ulaşılabilir.

Zaman O(nlog(n)).

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length-k];
}

Bu problem QuickSort algoritması benzeri QuickSelect algoritması kullanılarak da çözülebilir.

public int findKthLargest(int[] nums, int k) {
	if (k < 1 || nums == null) {
		return 0;
	}
 
	return getKth(nums.length - k +1, nums, 0, nums.length - 1);
}
 
public int getKth(int k, int[] nums, int start, int end) {
 
	int pivot = nums[end];
 
	int left = start;
	int right = end;
 
	while (true) {
 
		while (nums[left] < pivot && left < right) {
			left++;
		}
 
		while (nums[right] >= pivot && right > left) {
			right--;
		}
 
		if (left == right) {
			break;
		}
 
		swap(nums, left, right);
	}
 
	swap(nums, left, end);
 
	if (k == left + 1) {
		return pivot;
	} else if (k < left + 1) {
		return getKth(k, nums, start, left - 1);
	} else {
		return getKth(k, nums, left + 1, end);
	}
}
 
public void swap(int[] nums, int n1, int n2) {
	int tmp = nums[n1];
	nums[n1] = nums[n2];
	nums[n2] = tmp;
}

Zaman O(n),  En kötü durumda ise O(n^2).

Bu Problem Heap kullanılarak’da çözülebilmektedir.

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(k);
    for(int i: nums){
        q.offer(i);
 
        if(q.size()>k){
            q.poll();
        }
    }
 
    return q.peek();
}

Algoritma karmaşıklılığı O(nlog(k)).Alan karmaşıklılığı ise O(k)

Kaynak: https://www.programcreek.com/2014/05/leetcode-kth-largest-element-in-an-array-java/

http://www.cs.yale.edu/homes/aspnes/pinewiki/QuickSelect.html