快速排序 && 二分查找

颜色分类

class Solution { public void sortColors(int[] nums) { int len = nums.length; if (len < 2) { return; } //[0, left) 0 // [left, right) 1 // [right, nums.length) 2 int left = 0; int right = nums.length - 1; int i = 0; while (i <= right) { if (nums[i] == 0) { swap(nums, i++, left++); } else if (nums[i] == 1) { i++; } else { swap(nums, i, right--); } } } private void swap(int[] nums, int index1, int index2) { int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp; } }

数组中的第K个最大元素

class Solution { public int findKthLargest(int[] nums, int k) { int h = nums.length - k; return fun2(nums, 0, nums.length - 1, h); } public int fun2(int[] nums, int start, int end, int k) { int left = start; int right = end; int index = fun(nums, left, right); if (index == k) { return nums[index]; } if (k >= index) { return fun2(nums, index + 1, right, k); } else { return fun2(nums, left, index - 1, k); } } public int fun(int[] arr, int low, int high) { int tmp = arr[low]; while (low < high) { while (low < high && arr[high] >= tmp) { high--; } arr[low] = arr[high]; while (low < high && arr[low] <= tmp) { low++; } arr[high] = arr[low]; } arr[low] = tmp; return low; } public void swap(int[] nums, int source, int target) { int temp = nums[source]; nums[source] = nums[target]; nums[target] = temp; } }

根据字符出现频率排序

class Solution { public String frequencySort(String s) { int[] freq = new int[128]; for (int i = 0; i < s.length(); i++) { freq[s.charAt(i)]++; } int left = 0; int right = s.length(); char[] cs = s.toCharArray(); quickSort(cs, freq, left, right); return new String(cs); } // [left, right) public void quickSort(char[] charArray, int[] freq, int left, int right) { if (left >= right) { return; } int lt = left; int gt = right; int i = lt + 1; char pivot = charArray[left]; int pivotFreq = freq[pivot]; while (i < gt) { if (pivot == charArray[i]) { i++; } else if (pivotFreq < freq[charArray[i]]) { swap(charArray, i++, lt++); } else { gt--; swap(charArray, i, gt); } } quickSort(charArray, freq, left, lt); quickSort(charArray, freq, gt, right); } private void swap(char[] charArray, int index1, int index2) { char temp = charArray[index1]; charArray[index1] = charArray[index2]; charArray[index2] = temp; } }

删除排序数组中的重复项

class Solution { public int removeDuplicates(int[] nums) { int j = 0; for (int i = 1; i < nums.length; i++) { if (nums[i] != nums[i-1]) { j++; } nums[j] = nums[i]; } return j + 1; } }

移除元素

class Solution { public int removeElement(int[] nums, int val) { int j = 0; for (int i = 0; i < nums.length; i++) { nums[j] = nums[i]; if (nums[i] != val) { j++; } } return j; } }

移动零

class Solution { public void moveZeroes(int[] nums) { int j = 0; for (int i = 0; i < nums.length; i++) { nums[j] = nums[i]; if (nums[i] != 0) { j++; } } for (int i = j; i < nums.length; i++) { nums[i] = 0; } } }

寻找两个正序数组的中位数 符合我思维的方法

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int all = nums1.length + nums2.length; int[] target = all % 2 == 0 ? new int[] {all / 2 - 1, all / 2} : new int[] {all / 2}; int current = 0; int i = 0, j = 0; int last = 0; int now = 0; while (i < nums1.length || j < nums2.length) { if (i == nums1.length) { last = now; now = nums2[j++]; } else if (j == nums2.length) { last = now; now = nums1[i++]; } else if (nums2[j] < nums1[i]) { last = now; now = nums2[j++]; } else { last = now; now = nums1[i++]; } current++; if (current > all / 2) { break; } } if (target.length == 2) { return ((double) last + (double) now) / 2; } else { return now; } } }

二分查找法

在这里插入代码片

搜索插入位置

class Solution { public int searchInsert(int[] nums, int target) { return bSearch(nums, 0, nums.length - 1, target); } public int bSearch(int[] nums, int start, int end, int target) { if (start < end) { int mid = start + (end - start) / 2; if(target == nums[mid]) { return mid; } else if (target > nums[mid]) { return bSearch(nums, mid + 1, end, target); } else { return bSearch(nums, start, mid - 1, target); } } return target > nums[start] ? start + 1 : start; } }

搜索旋转排序数组

class Solution { public int search(int[] nums, int target) { return bSearch(nums, target, 0, nums.length - 1); } public int bSearch(int[] nums, int target, int start, int end) { if (start <= end) { int mid = start + (end - start) / 2; if (nums[mid] == target) { return mid; } if (nums[start] <= nums[mid]) { if (nums[start] <= target && target < nums[mid]) { return bSearch(nums, target, start, mid - 1); } else { return bSearch(nums, target, mid + 1, end); } } else { if (nums[mid] < target && target <= nums[end]) { return bSearch(nums, target, mid + 1, end); } else { return bSearch(nums, target, start, mid - 1); } } } return -1; } }

在排序数组中查找元素的第一个和最后一个位置

class Solution { public int[] searchRange(int[] nums, int target) { if (nums.length == 0) { return new int[] {-1, -1}; } return new int[] {lBSearch(nums, target, 0, nums.length - 1), rBSearch(nums, target, 0, nums.length - 1)}; } public int lBSearch(int[] nums, int target, int start, int end) { if (start <= end) { int mid = start + (end - start) / 2; if (nums[mid] < target) { return lBSearch(nums, target, mid + 1, end); } else { return lBSearch(nums, target, start, mid - 1); } } return (start < nums.length && nums[start] == target) ? start : -1; } public int rBSearch(int[] nums, int target, int start, int end) { if (start <= end) { int mid = start + (end - start) / 2; if (nums[mid] > target) { return rBSearch(nums, target, start, mid - 1); } else { return rBSearch(nums, target, mid + 1, end); } } return (end >= 0 && nums[end] == target) ? end : -1; } }

x 的平方根

class Solution { public int mySqrt(int x) { int left = 0; int right = x; while (left <= right) { int mid = left + (right - left) / 2; long now = (long) mid * (long) mid; if (now == x) { return mid; } else if (now < x) { left = mid + 1; } else { right = mid - 1; } } return left - 1; } }

剑指 Offer 11. 旋转数组的最小数字

class Solution { public int minArray(int[] numbers) { return fun(numbers, 0, numbers.length - 1); } public int fun(int[] numbers, int start, int end) { if (start <= end) { int mid = start + (end - start) / 2; if (numbers[mid] > numbers[end]) { return fun(numbers, mid + 1, end); } else if (numbers[mid] == numbers[end]) { return fun(numbers, start, --end); } else { return fun(numbers, start, mid); } } return start >= numbers.length ? numbers[start - numbers.length] : numbers[start]; } }

Pow(x, n)

class Solution { public double myPow(double x, int n) { long N = n; if (n < 0) { x = 1 / x; N = -N; } return fun(x, N); } public double fun(double x, long n) { if (n == 0) { return 1.0d; } double y = fun(x, n / 2); return n % 2 == 1 ? x * y * y : y * y; } }

两个数组的交集 II

class Solution { public int[] intersect(int[] nums1, int[] nums2) { if (nums2.length == 0 || nums1.length == 0) { return new int[0]; } quickSort(nums1, 0, nums1.length - 1); quickSort(nums2, 0, nums2.length - 1); int[] result = new int[nums1.length > nums2.length ? nums1.length : nums2.length]; int i=0, j=0; int l=0; while (i < nums1.length && j < nums2.length) { if (nums1[i] == nums2[j]) { result[l++] = nums2[j]; i++; j++; } else if (nums1[i] < nums2[j]) { i++; } else { j++; } } return Arrays.copyOf(result, l); } public void quickSort(int[] nums, int start, int end) { if (start > end) { return; } int pivot = nums[start]; int lt = start; int gt = end; int i = lt + 1; while (i <= gt) { if (nums[i] < pivot) { swap(nums, lt++, i++); } else if (nums[i] == pivot) { i++; } else { swap(nums, i, gt--); } } quickSort(nums, start, lt-1); quickSort(nums, gt+1, end); } public void swap(int[] nums, int source, int target) { int temp = nums[source]; nums[source] = nums[target]; nums[target] = temp; } }

剑指 Offer 53 - II. 0～n-1中缺失的数字

class Solution { public int missingNumber(int[] nums) { return bSearch(nums, 0, nums.length - 1); } public int bSearch(int[] nums, int start, int end) { if (start <= end) { int mid = start + (end - start) / 2; if (nums[mid] > mid) { return bSearch(nums, start, mid - 1); } else { return bSearch(nums, mid + 1, end); } } return start; } }