国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode] Sort Integers II [Merge-sort, Quick-sor

YorkChen / 1659人閱讀

Problem

Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.

Example

Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5].

Note

考察對Heap Sort, Quick Sort, Merge Sort的掌握。

Solution Merge Sort
public class Solution {
    public void sortIntegers2(int[] A) {
        if (A.length <= 1) return;
        int[] B = new int[A.length];
        sort(A, 0, A.length-1, B);
    }
    public void sort(int[] A, int start, int end, int[] B) {
        if (start >= end) return;
        int mid = start + (end - start) / 2;
        sort(A, start, mid, B);
        sort(A, mid+1, end, B);
        merge(A, start, mid, end, B);
    }
    public void merge(int[] A, int start, int mid, int end, int[] B) {
        int i = start, j = mid+1, index = start;
        while (i <= mid && right <= end) {
            if (A[i] < A[j]) B[index++] = A[i++];
            else B[index++] = A[j++];
        }
        while (i <= mid) B[index++] = A[i++];
        while (j <= end) B[index++] = A[j++];
        for (int k = start; k <= end; k++) A[k] = B[k];
    }
}
Heap Sort
public class Solution {
    private static int[] a;
    private static int n;
    private static int left;
    private static int right;
    private static int largest;
    public void sortIntegers2(int[] A) {
        a = A;
        buildheap(a);
        for(int i=n;i>0;i--){
            exchange(0, i);
            n=n-1;
            maxheap(a, 0);
        }
    }
    public static void buildheap(int []a){
        n=a.length-1;
        for(int i=n/2;i>=0;i--){
            maxheap(a,i);
        }
    }
    public static void maxheap(int[] a, int i){ 
        left=2*i;
        right=2*i+1;
        if(left <= n && a[left] > a[i]){
            largest=left;
        }
        else{
            largest=i;
        }
        
        if(right <= n && a[right] > a[largest]){
            largest=right;
        }
        if(largest!=i){
            exchange(i,largest);
            maxheap(a, largest);
        }
    }
    public static void exchange(int i, int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t; 
    }
}
Quick Sort
public class Solution {
    public void sortIntegers2(int[] A) {
        if (A.length <= 1) return;
        quicksort(A, 0, A.length-1);
    }
    public void quicksort(int[] A, int start, int end) {
        if (start >= end) return;
        int mid = start+(end-start)/2;
        int pivot = A[mid], i = start, j = end;
        while (i <= j) {
            while (i <= j && A[i] < pivot) i++;
            while (i <= j && A[j] > pivot) j--;
            if (i <= j) {
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                i++;
                j--;
            }
        }
        quicksort(A, start, j);
        quicksort(A, i, end);
    }
}

文章版權歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/64977.html

相關文章

  • [LintCode/LeetCode] Combination Sum I & II

    摘要:和唯一的不同是組合中不能存在重復的元素,因此,在遞歸時將初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

    ThreeWords 評論0 收藏0
  • [LintCode/LeetCode] Subsets & Subsets II

    Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

    tracy 評論0 收藏0
  • [LintCode] Majority Number I II III

    摘要:遍歷整個數(shù)組,用一個計數(shù)器,找出超過整個數(shù)組長度二分之一的那個數(shù)。規(guī)則是當前數(shù)等于,計數(shù)器加否則,計數(shù)器減。當?shù)拇笮〉扔跁r,統(tǒng)計中所有的,并將所有對應的減,若被減為,就從中移除這對鍵值。 Majority Number I Problem Given an array of integers, the majority number is the number that occurs ...

    sPeng 評論0 收藏0
  • [LintCode/LeetCode] Jump Game I & II

    摘要:建立動規(guī)數(shù)組,表示從起點處到達該點的可能性。循環(huán)結束后,數(shù)組對所有點作為終點的可能性都進行了賦值。和的不同在于找到最少的步數(shù)。此時的一定是滿足條件的最小的,所以一定是最優(yōu)解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

    rose 評論0 收藏0
  • [LintCode/LeetCode] House Robber II

    摘要:因為取了隊首就不能取隊尾,所以對數(shù)組循環(huán)兩次,一個從取到,一個從取到,比較兩次循環(huán)后隊尾元素,取較大者。注意,要先討論當原數(shù)組位數(shù)小于時的情況。 Problem After robbing those houses on that street, the thief has found himself a new place for his thievery so that he wi...

    OnlyLing 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<