프로그래밍의 아름다움[02]_계속하다

2. 제목: 많은 무질서한 수 중에서 (먼저 서로 같지 않다고 가정하고) 그 중에서 가장 큰 K개의 수를 선택한다.
해법 5,
생각:
1. 빠른 배열의 분치 사상을 채택하여 먼저 무서수 중의 랜덤수를 취하여 무서수를 1, 2 두 부분으로 나누는데 그 중에서 1부의 점수는 이 랜덤수 집합보다 작고 2부의 점수는 이 랜덤수 집합보다 크다.
2. 만약에 제1부분의 수(이 랜덤 수를 더한) 개수가 K라면 바로 앞의 K 개수를 되돌려주면 원하는 것이다.첫 번째 부분의 수가 K보다 크면 첫 번째 분수의 최대 K 수를 찾습니다.1부 점수 개수가 K보다 작으면 2부 점수 중 가장 큰 K-length 개수를 찾고,length는 1부 점수 개수를 찾습니다.
이 알고리즘의 시간 복잡도는 O(n*logn)로 빠른 배열과 마찬가지로 이 정렬 알고리즘은 무작위 수의 선택에 의존하여 불안정성을 가진다.
계산:
1. 전체 수조에 대해 분할 알고리즘(간단하게 첫 번째 수를 분할 랜덤수로 직접 추출할 수 있음).
2. 분할된 후 1부의 분수 개수가 K–1이면 수조 앞의 K 개수가 요구된다.만약 분할된 후 1부의 분수 개수가 K–1보다 작으면 2부의 분수 중 K–split의 최대 수를 찾아낸다.분할된 후 1부 점수가 K–1보다 크면 1부 점수 중 K개의 최대 수를 찾습니다.
코드:

    private int partition(int[] arr, int begin, int end) {
        int key = begin, tmp;
        for(int low = begin, high = end; low < high; ) {
            if(arr[low] < arr[high]) {
                tmp = arr[low];               //swap arr[low] and arr[high]
                arr[low] = arr[high];
                arr[high] = tmp;
                
                if(key == low) {
                    low++;
                    key = high;
                } else {
                    high--;
                    key = low;
                }
            } else {
                if(key == low) {
                    high--;
                } else {
                    low++;
                }
            }
        }
        
        return key;
    }
    public void topK4(int []arr, int begin, int end, int k) {
        int split = partition(arr, begin, end);
        
        if((split - begin + 1) == k) {
            return;
        } else if(split - begin + 1 < k) {
            topK4(arr, split + 1, end, k - (split - begin) - 1);
        } else {
            topK4(arr, 0, split - 1, k);
        }

    }

사고방식: 다중 병합 사고방식을 이용하여 먼저 무서수를 M등분으로 나누어 매등분 내의 수를 정렬한다(간단하게 빠른 배열을 사용할 수 있고 그 시간 복잡도는 Q*logQ, 그 중에서 Q는 매등분 내의 수의 개수). 그리고 패자수를 병합 정렬하여 매등분수에서 최대수를 추출하여 잎노드로 병합 정렬하고 노드와 아버지 노드를 비교한다.loser는 아버지 노드에 남는다.winner는 계속해서 더 높은 등급의 비교를 진행할 수 있다.
계산:
1. 무서수에 대해 M 등분의 구분을 한다.
2. 각 등분수 중 최대수를 순서대로 꺼내서 패자 나뭇잎 노드로siftup을 하고 winner 노드를 출력하며 이 승자 노드가 있는 등분에서 현재 최대수를 꺼내서 winner를 교체한다. 출력된 winner 노드의 개수가 K가 될 때까지.

    public class LoseTree {
        
        private int[] branches;
        private int[] nodes;
        
        public void getNumFromBuffer(List<Integer> buffer, int bufferIndex) throws Exception {    //get number
            if(buffer.size() == 0) {
                throw new Exception("the buffer is null");
            }
            
            branches[bufferIndex] = buffer.remove(0);
        }
        
        public int competitionBranch(int branchIndex) {
            int father = (nodes.length + branchIndex - 1) / 2;
            while(father >= 0) {
                if(branches[nodes[father]] > branches[branchIndex]) {                      //swap the nodes[father] and the branchIndex
                    int tmp = nodes[father];
                    nodes[father] = branchIndex;
                    branchIndex = tmp;
                }
                
                if(father == 0) break; 
                else father = (father - 1) / 2;
            }
            
            return branchIndex;
        }
        
        public int getBranch(int branchIndex) {
            return branches[branchIndex];
        }
        
        public int init(List<Integer>[] buffers) throws Exception {
            branches = new int[buffers.length];               
            
            for(int i = 0; i < branches.length; i++) {     
                getNumFromBuffer(buffers[i], i);
            }
            
            nodes = new int[branches.length - 1];
            
            int max = -1;
            for(int i = 0; i < branches.length; i++) {     
                if(max < branches[i]) { max = i; }
            }
            for(int i = 0; i < nodes.length; i++) {        
                nodes[i] = max;
            }
            
            int winnerIndex = 0;                         
            for(int i = 0; i < nodes.length; i++) {
                winnerIndex = competitionBranch(i);
            }
            
            return winnerIndex;
        }
        
        public LoseTree() {

        }
        
    }
    
    @SuppressWarnings({ "unchecked", "rawtypes"})
    public List<Integer>[] createBuffer(int[] arr, int k) {         
        
        List[] buffers = arr.length % k == 0 ? new List[arr.length / k] : new List[arr.length / k + 1];
        for(int i = 0; i < buffers.length; i++) {      
            buffers[i] = new ArrayList();
        }
        
        for(int i = 0; i < arr.length; i++) {      
            buffers[i / k].add(arr[i]);
        }
        
        int addition = arr.length % k;              
        if(addition != 0) {
            int end = arr.length / k;
            for(int i = addition; i < k; i++) {
                buffers[end].add(0);
            }
        }
        
        for(int i = 0; i < buffers.length; i++) {      
            Collections.sort(buffers[i], Collections.reverseOrder());
        }
        
        return buffers;
    }
    
    public List<Integer> topK(int []arr, int k) throws Exception {
        List<Integer>[] buffers = createBuffer(arr, k);          
        
        if(buffers.length == 1) {                  
            return buffers[0];
        }
        
        LoseTree loseTree = new LoseTree();
        int winnerIndex = loseTree.init(buffers);       
        
        List<Integer> topKArr = new ArrayList<Integer>();
        for(int i = 0; i < k - 1; i++) {
            winnerIndex = loseTree.competitionBranch(winnerIndex);      
            topKArr.add(loseTree.getBranch(winnerIndex));
            loseTree.getNumFromBuffer(buffers[winnerIndex], winnerIndex);       
        }
        winnerIndex = loseTree.competitionBranch(winnerIndex);
        topKArr.add(loseTree.getBranch(winnerIndex));
        
        return topKArr;
    }