成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LC總結(jié)] 排序 Median [QuickSort] Sort Integers II

opengps / 2381人閱讀

Problem

Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tree.
Given a unsorted array with integers, find the median of it.

A median is the middle number of the array after it is sorted.

If there are even numbers in the array, return the N/2-th number after sorted.

Example

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

Given [7, 9, 4, 5], return 5.

Challenge

O(n) time.

Note

理解快排。注意，作為pivot的元素在遞歸時(shí)要exclude出來。

Solution

Last as pivot

public class Solution {
    public int median(int[] nums) {
        return helper(nums, 0, nums.length-1, (nums.length-1)/2);
    }
    public int helper(int[] A, int start, int end, int k) {
        int l = start, r = end;
        int pivot = end, a = A[pivot];
        while (l < r) {
            while (l < r && A[l] < a) l++;
            while (l < r && A[r] >= a) r--;
            swap(A, l, r);
        }
        swap(A, l, end);
        if (l == k) return A[l];
        else if (l < k) return helper(A, l+1, end, k);
        else return helper(A, start, l-1, k);
    }
    public void swap(int[] A, int l, int r) {
        int temp = A[l];
        A[l] = A[r];
        A[r] = temp;
    }
}
Sort Integers II Merge sort 
public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // Write your code here
        if (A.length <= 1) return;
        int[] B = new int[A.length];
        sort(A, 0, A.length-1, B);
    }
    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);
    }
    void merge(int[] A, int start, int mid, int end, int[] B) {
        int i = start, j = mid+1, index = start;
        while (i <= mid && j <= end) {
            if (A[i] < A[j]) B[index++] = A[i++];
            else B[index++] = A[j++];
        }
        while (j <= end) B[index++] = A[j++];
        while (i <= mid) B[index++] = A[i++];

        for (int k = start; k <= end; k++) A[k] = B[k];
    }
}
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 i = start, j = end;
        int pivot = A[start+(end-start)/2];
        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);
    }
}
Heap Sort 
public class Solution {
    public void sortIntegers2(int[] A) {
        buildheap(A);
        int n = A.length-1;
        for(int i = n; i > 0; i--){
            exchange(A, 0, i);
            n = n-1;
            maxheap(A, 0, n);
        }
    }
    public static void buildheap(int[] a){
        int n = a.length-1;
        for(int i = n/2; i>=0; i--){
            maxheap(a, i, n);
        }
    }
    public static void maxheap(int[] a, int i, int n){ 
        int left = 2*i;
        int right = 2*i+1;
        int max = 0;
        if(left <= n && a[left] > a[i]) max = left;
        else max = i;
        if(right <= n && a[right] > a[max]) max = right;
        if(max != i){
            exchange(a, i, max);
            maxheap(a, max, n);
        }
    }
    public static void exchange(int[] a, int i, int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t; 
    }
}

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65870.html

相關(guān)文章

  • 【LC總結(jié)】回溯 (Subsets I II/Permutation I II/Combinatio

    摘要：不同數(shù)包含重復(fù)數(shù)為的時(shí)候，表示在外層的循環(huán)正在被使用，所以當(dāng)前循環(huán)遇到為一定要跳過。對當(dāng)前循環(huán)要添加的數(shù)組，在添加當(dāng)前元素后進(jìn)行遞歸，遞歸之后要將當(dāng)前元素的使用標(biāo)記改為，表示已經(jīng)使用和遞歸完畢，然后再將這個(gè)元素從的末位刪除。 Subsets Problem Given a set of distinct integers, nums, return all possible subse...

    tuomao 評論0 收藏0

  • 【LC總結(jié)】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

    摘要：找符合條件的總數(shù)。雙指針區(qū)間考慮邊界，長度，為空，等。之后的范圍用雙指針和表示。若三個(gè)指針的數(shù)字之和為，加入結(jié)果數(shù)組。不要求，所以不用判斷了。同理，頭部兩個(gè)指針向后推移，后面建立左右指針夾逼，找到四指針和為目標(biāo)值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...

    awesome23 評論0 收藏0

  • JavaScript專題之解讀 v8 排序源碼

    摘要：插入排序是穩(wěn)定的算法。所以準(zhǔn)確的說，當(dāng)數(shù)組長度大于的時(shí)候，采用了快速排序和插入排序的混合排序方法。在對數(shù)組進(jìn)行了一次快速排序后，然后對兩個(gè)子集分別進(jìn)行了插入排序，最終修改數(shù)組為正確排序后的數(shù)組。 JavaScript 專題系列第二十篇，也是最后一篇，解讀 v8 排序源碼 前言 v8 是 Chrome 的 JavaScript 引擎，其中關(guān)于數(shù)組的排序完全采用了 JavaScript 實(shí)...

    princekin 評論0 收藏0

  • 【LC總結(jié)】圖、拓?fù)?em>排序 (Course Schedule I, II/Alien Dictiona

    Course Schedule Problem There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, whi...

    gaara 評論0 收藏0

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

    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, Q...

    YorkChen 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<