Java를 사용하여 Top-K 문제를 해결하는 방법

질문

가장 작은 K 숫자 찾기

배열에서 가장 작은 K 숫자를 찾는 알고리즘을 설계하세요. 이 k개 숫자는 어떤 순서로든 반환될 수 있습니다.

문제 해결 방법

방법 1

Sort(bubble/select)

Idea

1. Bubble 정렬은 K번 실행될 때마다 최종 위치를 결정하는 것입니다. , 시간 복잡도는 O(n * k)입니다. k

2. 선택 정렬이 실행될 때마다 가장 큰 숫자 또는 가장 작은 숫자가 결정되어 한쪽 끝에 배치됩니다. 선택 정렬을 통해 K 번 실행하면 최대 K 숫자를 얻을 수 있습니다. 시간 복잡도는 O(N*K)입니다.

코드 구현

  //冒泡排序
    public static int[] topKByBubble(int[] arr, int k) {
        int[] ret = new int[k];
        if (k == 0 || arr.length == 0) {
            return ret;
        }
        for (int i = 0; i < k; i++) {
            for (int j = arr.length - 1; j < i; j--) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
            ret[i] = arr[i];
        }
        return ret;
    }
    //选择排序
    public static int[] topKBySelect(int[] arr, int k) {
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            int maxIndex = i;
            int maxNum = arr[maxIndex];
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] > maxNum) {
                    maxIndex = j;
                    maxNum = arr[j];
                }
            }
            if (maxIndex != i) {
                swap(arr, maxIndex, i);
            }
            ret[i] = arr[i];
        }
        return ret;
    }
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

방법 2

분할 정복 - Quick Sort

Idea

1. 퀵 정렬의 핵심은 먼저 분할 정복을 통해 시퀀스를 두 부분으로 나누고, 그런 다음 두 부분을 다시 반복합니다.

2, 분할 및 정복 아이디어를 사용합니다. 즉, 작업 분할을 나누고 주요 요소 피벗에 따라 순서를 조정하고 피벗보다 큰 부분을 왼쪽 끝에 놓습니다. 오른쪽 끝의 피벗보다 작은 숫자를 사용하여 주 요소 피벗의 위치인ivotIndex를 결정합니다. 이것이 우리에게 필요한 상위 K입니다.

시간 복잡도: O(n)

코드 구현

public static int[] topKByPartition(int[] arr, int k){
    if(arr.length == 0 || k <= 0){
        return new int[0];
    }
    return quickSort(arr,0,arr.length-1,k);

}
//快速排序
public static int[] quickSort(int[] arr, int low, int high, int k){
    int n = arr.length;
    int pivotIndex = partition(arr, low, high);
    if(pivotIndex == k-1){
        return Arrays.copyOfRange(arr,0,k);
    }else if(pivotIndex > k-1){
        return quickSort(arr,low,pivotIndex-1,k);
    }else {
        return quickSort(arr,pivotIndex+1,high,k);
    }
}
public static int partition(int[] arr, int low, int high){
   if(high - low == 0){
       return low;
   }
   int pivot = arr[high];
   int left = low;
   int right = high-1;
   while (left < right){
       while (left < right && arr[left] > pivot){
           left++;
       }
       while (left < right && arr[right] < pivot){
           right--;
       }
       if(left < right){
           swap(arr,left,right);
       }else {
           break;
       }
   }
   swap(arr,high,left);
   return left;
}
public static void swap(int[] arr,int a, int b){
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

방법 3

힙 사용

Idea

1, 최대 힙 구축

2, 원본 배열 순회, 요소 삽입, 크기가 힙이 K인 경우 힙의 최상위 요소를 다음 요소와 비교하기만 하면 됩니다. 힙의 최상위 요소보다 크면 힙의 최상위 요소를 삭제하고 다음 요소가 나올 때까지 해당 요소를 힙에 삽입합니다. 모든 요소가 순회됩니다

3. 큐에 저장된 K는 큐에서 제거된 항목 수

시간 복잡도: O(N*logK)

코드 구현

public class TopK {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(k==0 || arr.length==0){
            return ret;
        }
        // 1,构建一个最大堆
        // JDK的优先级队列是最小堆， 就要用到我们比较器
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //2,遍历原数组，进行入队
        for(int value:arr){
            if(queue.size() < k){
                queue.offer(value);
            }else{
                if(value < queue.peek()){
                    queue.poll();
                    queue.offer(value);
                }
            }
        }
        //3,将queue中存储的K个元素出队
        for(int i = 0;i < k;i++){
            ret[i] = queue.poll();
        }
        return ret;
    }
}

위 내용은 Java를 사용하여 Top-K 문제를 해결하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!