Leetcode 笔记 Posted on 2020年11月6日 | In Coding ### 排序 #### 堆排序 1. 建堆(升序-大顶堆,降序-小顶堆) 2. 堆顶与末尾交换,重新建堆 - 时间复杂度:O(n log n) - 空间复杂度:O(n) ```Java class Solution { public int[] HeapSort(int[] nums) { int[] heap = Arrays.copyOf(nums, nums.length); int len = heap.length; buildMaxHeap(heap); for (int i=heap.lengh-1; i>=0; i--) { swap(heap, 0, i); len--; heapify(heap, 0, len); } return heap; } public void buildMaxHeap(int[] heap) { for (int i=heap.length/2; i>=0; i--) { heapify(heap, i, heap.length); } } public void heapify(int[] heap, int i, int len) { int l = 2 * i + 1; int r = 2 * i + 2; int largest = i; if (l < len && heap[l] > heap[largest]) { largest = l; } if (r < len && heap[r] > heap[largest]) { largest = r; } if (largest != i) { swap(heap, largest, i); heapify(heap, largest, len); } } public void swap(int[] heap, int x, int y) { int temp = heap[x]; heap[x] = heap[y]; heap[y] = temp; } } ``` #### 快排 - 分治思想 - 时间复杂度:O(n log n) - 空间复杂度:O(n) 1. 选择基准,通常是第一个值 2. 左右同时向中间搜索,找到左边第一个大于基准和右边第一个小于基准的,交换 3. 左右指针相遇后与基准值交换 4. 划分为两个小数组,重复2、3 ```Java class Solution { public int[] quickSort(int[] nums) { partion(nums, 0, nums.length-1); return nums; } public void partion(int[] nums, int start, int end) { if (start > end) return; int i = start; int j = end; while (i < j) { while (nums[j] >= nums[start] && i < j) j--; while (nums[i] <= nums[start] && i < j) i++; if (i < j) { swap(nums, i, j); } } swap(nums, i, start); partion(nums, start, i-1); partion(nums, i+1, end); } public void swap(int[] nums, int x, int y) { int temp = nums[x]; nums[x] = nums[y]; nums[y] = temp; } } ``` ### 随机采样 #### 水塘采样 - 适用于无法将全部元素存入内存,需要随机采样 - 时间复杂度:O(n) - 空间复杂度:O(k),k为采样数 ```Java class Solution { Random random = new Random(); ListNode head; public void Solution(ListNode head) { this.head = head; } public int getRandom() { ListNode node = head; int val = node.val; int n = 1; while (node != null) { if (random.nextFloat() <= 1.0/n) { val = node.val; } n++; node = node.next; } return val; } } ``` ### 查找 #### 二分查找 - 适用于已排序数组 - 时间复杂度:O(log n) ```java class Solution { public int binarySearch(int[] nums, int target) { int l = 0; int r = nums.length-1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { l = mid + 1; } else { r = mid - 1; } } return -1; } } ```