문제: 하나의 수조 길이가 n으로 가장 작은 k개의 원소를 구하고 작은 것에서 큰 출력으로

2929 단어 프로그램이론
이러한 문제에 부딪히다: 하나의 수조 길이가 n으로 가장 작은 k개의 원소를 구하고 작은 것에서 큰 출력으로
다음 세 가지 해결 방법을 생각해 보십시오.
1. 가장 간단한 것은 수조에 순서를 정하고 앞의 k개 원소를 출력한다. OK.
장점은 간단명료하다는 것이다.단점은 많은 추가 작업을 했다는 것이다. k개 원소 뒤에 있는 것은 필요없다.
2. 위보다 나은 것은 한 무더기를 사용하거나 나무를 정렬하는 것이다.우선 그룹의 앞 k개 요소를 이 더미에 삽입하거나 두 갈래 트리를 정렬합니다.그리고 뒤에 있는 모든 원소에 대해
a. 이 요소를 더미에 삽입하거나 두 갈래 나무에 정렬하기;
b. 이 무더기나 정렬 두 갈래 나무에서 가장 큰 원소를 제거합니다.
무더기로 이루어진다면 무더기 정렬을 참고할 수 있다.정렬 트리를 사용하면 기존의 TreeSet: (주: 여기 요구 사항이 있습니다. 입력 그룹의 요소가 모두 같지 않습니다)
private static void solveSet(int[] data, int count) {
        TreeSet set = new TreeSet();
        for (int i=0; i

무더기와 정렬 트리의 삽입 삭제가 비교적 빠르기 때문에, 그 성능은 전체 수조 정렬보다 틀림없이 강할 것이다.
내 테스트 결과, 1억 개의 데이터로 시간 대비
ms used for treeset 660 ms used for sort 2153
오케이, 그럼 더 빠른 방법은 없을까?예전의 그룹에서 k번째 작은 요소를 선택하는 호어 알고리즘을 생각해 냈다.
또한 유사하다. 수조에서 k번째 작은 요소를 선택하면 전체 수조를 정렬할 필요가 없고 빠른 정렬과 유사한 과정이다.
a) 우선 그룹에서 하나의 수 m 선택
b) 수조의 원소를 정리하고 m보다 작은 것은 왼쪽에 놓고 m보다 큰 것은 오른쪽에 놓는다.작은 부분과 큰 부분의 순서는 상관없고 m보다 작은 것만 요구하면 된다.
c) 정리한 후에 m의 위치가 마침 k라면 k의 작은 것은 m이다. 직접 m로 돌아가 끝낸다.
d) 그렇지 않으면 m의 위치 > k, 찾을 요소가 왼쪽에 있음을 나타냅니다.왼쪽 부분을 똑같이 처리한다.
만약 m의 위치처음의 문제로 돌아가다.이런 사고방식이 생기면 우리는 수조에 대해 k의 작은 원소를 찾을 수 있다.이때 위의 알고리즘은 다시 k 왼쪽의 요소가 모두 k보다 작다는 것을 보증했다.그렇게 간단하면 왼쪽의 원소에 대해 순서를 정하면 OK가 된다.물론 이것은 찾으려는 원소의 개수에 비교적 적합하고 수조의 길이보다 훨씬 작은 상황(예를 들어 1억 개의 원소 중에서 가장 작은 10개를 찾는 것)이다.
먼저 k 번째 작은 코드를 찾으면 다음과 같습니다.
class Hoare {

    public static void main(String[] argu) {
        int testSize = 100;
        int[] t1 = new int[100];
        Random r = new Random();
        for (int i=0; i

이 알고리즘을 사용하여 k번째 작은 것을 찾습니다.찾은 후에 앞의 원소가 모두 k보다 작다는 것을 보증할 수 있기 때문에 앞의 원소에 대해 다시 순서를 정해야 한다.이번에 정렬할 원소가 매우 적기 때문에 속도가 빠르다.
private static void solveHoare(int[] data, int count) {
        int k = Hoare.select(data, count, 0, data.length - 1);
        int[] temp = Arrays.copyOfRange(data, 0, count);
        Arrays.sort(temp);
        System.out.println("Final data " + Arrays.toString(temp));
    }

비교해 보면 찾으려는 원소의 개수가 수조의 길이보다 훨씬 적은 경우 이런 알고리즘이 가장 빠르다.
수조의 길이가 1억일 때 가장 작은 100개 원소를 열거하고 시간은 다음과 같다.
ms used for treeset 9315 ms used for sort 2373 ms used for selectk 201
전차순(후차순)을 통해 중차순 역행 두 갈래 트리 구해 차원 역행
나는 이 항목의 테스트를 통과하기가 매우 어렵다는 것을 발견했다. 누가 나를 도와줄 수 있겠는가

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage