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; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/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...
閱讀 1924·2021-10-11 10:59
閱讀 1033·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
閱讀 1466·2019-08-28 18:13
閱讀 733·2019-08-26 13:35