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.
ExampleGiven [4, 5, 1, 2, 3], return 3.
Given [7, 9, 4, 5], return 5.
ChallengeO(n) time.
Note理解快排。注意,作为pivot的元素在递归时要exclude出来。
SolutionLast 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; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65870.html
摘要:不同数包含重复数为的时候,表示在外层的循环正在被使用,所以当前循环遇到为一定要跳过。对当前循环要添加的数组,在添加当前元素后进行递归,递归之后要将当前元素的使用标记改为,表示已经使用和递归完毕,然后再将这个元素从的末位删除。 Subsets Problem Given a set of distinct integers, nums, return all possible subse...
摘要:找符合条件的总数。双指针区间考虑边界,长度,为空,等。之后的范围用双指针和表示。若三个指针的数字之和为,加入结果数组。不要求,所以不用判断了。同理,头部两个指针向后推移,后面建立左右指针夹逼,找到四指针和为目标值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...
摘要:插入排序是稳定的算法。所以准确的说,当数组长度大于的时候,采用了快速排序和插入排序的混合排序方法。在对数组进行了一次快速排序后,然后对两个子集分别进行了插入排序,最终修改数组为正确排序后的数组。 JavaScript 专题系列第二十篇,也是最后一篇,解读 v8 排序源码 前言 v8 是 Chrome 的 JavaScript 引擎,其中关于数组的排序完全采用了 JavaScript 实...
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...
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...
阅读 1923·2021-10-11 10:59
阅读 1032·2021-09-07 09:59
阅读 2226·2021-08-27 16:17
阅读 2783·2019-08-30 15:54
阅读 2274·2019-08-30 12:58
阅读 1773·2019-08-30 12:53
阅读 1465·2019-08-28 18:13
阅读 733·2019-08-26 13:35