分治算法
寻找两个有序数组的中位数
// 二分查找的思路，halfLen 是中位数的right 所以必须 m + n + 1 // 中位数是可以将数组分割为左右相等的数组，一个数将其分为左右相等个数有很多 // 同时要满足坐最大值小于右最小值
int m = nums1.length;
int n = nums2.length;
if(m > n){
return findMedianSortedArrays(nums2, nums1);
}
// 两个数组中找中位数转换为一个数组
int left = 0,right = m;
// 这里用 m + n 表示 大于中间值一位
int halfLen = (m + n + 1)/2 ;
int i = 0,j = 0;
while(left <= right){
i = left + (right - left)/2;
j = halfLen - i;
if(i < right && nums1[i] < nums2[j-1] ){
left = i + 1;
}else if(i > left && nums1[i-1] > nums2[j]){
right = i -1;
}else{
// 找到 最大的left 和 最小right
int maxLeft = 0;
if(i == 0){
maxLeft = nums2[j-1];
}else if(j == 0){
maxLeft = nums1[i-1];
}else{
maxLeft = Math.max(nums1[i-1], nums2[j-1]);
}
if((m+n)%2 == 1) return maxLeft;
int minRight = 0;
if (i == m) { minRight = nums2[j]; }
else if (j == n) { minRight = nums1[i]; }
else { minRight = Math.min(nums2[j], nums1[i]); }
// 返回 (left + right) / 2.0
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;// 分治思想找到 两个数组的中位数，实际转换为分治求两个数组第k小的问题
// 分治思想
// 中位数实际就是第K小问题，当奇数时是中间数，当偶数是中间两数除以2
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
// 求 k 1 2 3 4 1 2 3 4 5
int left = (m + n + 1)/2;
int right = (m + n + 2)/2;
return (getMinThK(nums1,0,m-1,nums2,0,n-1,left) +
getMinThK(nums1,0,m-1,nums2,0,n-1,right))/2.0;
}
public int getMinThK(int[] A,int s1,int e1,int[] B,int s2,int e2,int k){
int len1 = e1 - s1 + 1;
int len2 = e2 - s2 + 1;
// 两个数组求第k小，只操作第一个数组
if(len1 > len2){
return getMinThK(B, s2, e2, A, s1, e1, k);
}
// 默认第一个数组是长度较小数组
if(len1 == 0){
return B[s2 + k - 1];
}
// 最小，两个数组最小
if(k == 1){
return Math.min(A[s1], B[s2]);
}
// 每次排除一半,找到两个数组中 k/2 位置
int lk = s1 + Math.min(len1, k/2) - 1;
int rk = s2 + Math.min(len2, k/2) - 1;
// 这两个位置 谁小说明 小于它的一定不会是第k小
if(A[lk]<B[rk]){
return getMinThK(A, lk+1, e1, B, s2, e2, k - (lk - s1 + 1));
}else{
return getMinThK(A, s1, e1, B, rk+1, e2, k - (rk - s2 + 1));
}
}合并K个有序的链表
// 分治思想，先两个合并，在两两合并
使用 interval 来控制合并的数组，将数据都合并到第一个链表上， interval * 2 来表示下一组，停止条件是interval => n
public ListNode mergeTwoLists(ListNode l1, ListNode l2){
if (l1 == null){
return l2;
}else if (l2 == null){
return l1;
}
ListNode root = new ListNode(-1);
ListNode p = root;
while (l1 != null && l2 != null){
if (l1.val < l2.val){
p.next = new ListNode(l1.val);
l1 = l1.next;
}else {
p.next = new ListNode(l2.val);
l2 = l2.next;
}
p = p.next;
}
p.next = l1 != null ? l1 : l2;
return root.next;
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0){
return null;
}
if (lists.length == 1){
return lists[0];
}
// 进行 两两合并
// 间隔呈现倍数增长
int interval = 1;
while (interval < lists.length) {
for (int i = 0; i < lists.length-interval; i += interval * 2) {
lists[i] = mergeTwoLists(lists[i],lists[i+interval]);
}
interval *=2;
}
return lists[0];
}最大子序数组和
暴力
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0){
return 0;
}
int n = nums.length;
// 加1 的目的是让其可以有办法得到其本身
int[] sums = new int[n+1];
sums[0] = 0;
for (int i=1;i<=n;i++){
sums[i] = sums[i-1] + nums[i-1];
}
int max = Integer.MIN_VALUE;
for (int i=1;i<=n;i++){
for (int j=0;j<i;j++){
System.out.println(sums[i] - sums[j]);
if (sums[i] - sums[j] > max){
max = sums[i] - sums[j];
}
}
}
return max;
}// dp 如果前面的sum > 0 才会对后面的和产生增益，否则 不会 sum = num
public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int num: nums) {
if(sum > 0) {
sum += num;
} else {
sum = num;
}
ans = Math.max(ans, sum);
}
return ans;
}// 分治，使用分治的方法进行计算局部最大和
public int maxSubArray(int[] nums){
if (nums == null || nums.length == 0){
return 0;
}
int n = nums.length;
return maxSubArraySum(nums,0,n-1);
}
public int maxSubArraySum(int[] nums,int left,int right){
if (left == right){
return nums[left];
}
int mid = (left + right) >>> 1
return max3(maxSubArraySum(nums,left,mid),maxSubArraySum(nums,mid+1,right),maxCrossingSum(nums,left,mid,right));
}
public int maxCrossingSum(int[] nums,int left,int mid,int right){
int sum = 0;
int sumLeft = Integer.MIN_VALUE;
for (int i = mid;i>= left;i--){
sum += nums[i];
if (sum > sumLeft){
sumLeft = sum;
}
}
int sumRight = Integer.MIN_VALUE;
sum = 0;
for (int i=mid+1;i<=right;i++){
sum += nums[i];
if (sum > sumLeft){
sumLeft = sum;
}
}
return sumLeft + sumRight;
}求众数
// 众数一定可以抵消调其他数，因为其大于n/2
// 众数是 一次遍历， 记录上一个值，相同加1，不同减一，当为0 时重新设置 1，更新当前值
public int majorityElement(int[] nums) {
int count = 0;
int majorNum = nums[0];
for (int i=0;i<nums.length;i++){
if (count == 0){
count = 1;
majorNum = nums[i];
}else {
if (nums[i] == majorNum){
count ++;
}else {
count --;
}
}
}
return majorNum;
}// 使用分治算法
public int majorityElement(int[] nums){
return majorityElement(nums,0,nums.length-1);
}
public int majorityElement(int[] nums,int left,int right){
if (left == right){
return nums[left];
}
int mid = (left + right) >>> 1;
int majorLeft = majorityElement(nums,left,mid);
int majorRight = majorityElement(nums,mid+1,right);
if (majorLeft == majorRight){
return majorLeft;
}
int countLeft = countInRange(nums, majorLeft, left, right);
int countRight = countInRange(nums,majorRight,left,right);
return countLeft<countRight ? majorRight:majorLeft;
}
private int countInRange(int[] nums, int num, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
```
#### 查找數組中的第K大
// 使用大顶堆来进行 查找 第 K 大，优先队列默认是从大到小
``
// 使用大顶堆进行查找
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
for (int i=0;i<nums.length;i++){
queue.offer(nums[i]);
if (queue.size() > k){
queue.poll();
}
}
return queue.peek();
}// 使用快排的分治思想
// 使用快排思想分治分治算法
public int findKthLargest(int[] nums, int k){
// 快排找寻的是下标
return findKthLargest(nums,0,nums.length-1,k-1);
}
public int findKthLargest(int[] nums,int left,int right,int k){
// 初始中轴
int privot = nums[0];
// 保存初始边界
int temp_left = left;
int temp_right = right;
while (left < right){
while (left < right && nums[right] <= privot){
right --;
}
nums[left] = nums[right];
while (left < right && nums[left] >= privot){
left ++;
}
nums[right] = nums[left];
}
if (left == k){
return nums[left];
}else if (left > k){
return findKthLargest(nums,temp_left,left-1,k);
}else {
return findKthLargest(nums,left+1,temp_right,k);
}
}搜索二维矩阵2
按层进行二分查询
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return false;
}
int m = matrix.length;
int n = matrix[0].length;
for (int i=0;i<m;i++){
if (target >= matrix[i][0] && target <= matrix[i][n-1]){
int index = Arrays.binarySearch(matrix[i],target);
if (index > 0){
return true;
}
}
}
return false;
}// 搜索二维矩阵问题注意左下的问题
public boolean searchMatrix2(int[][] matrix, int target){
if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
return false;
}
int m = matrix.length;
int n = matrix.length;
// 从左下开始寻找，大于向右 小于向左
int i = m-1,j = 0;
while (i >= 0 && j < n){
int x = matrix[i][j];
if (x == target){
return true;
}else if (x < target){
j++;
}else {
i--;
}
}
return false;
}// 分治思想查找矩阵
思路是矩阵的最大值是在右下，矩阵的最小值是左上
public boolean searchMatrix4(int[][] matrix, int target){
this.matrix = matrix;
this.target = target;
if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
return false;
}
return searchRec(0,0,matrix.length-1,matrix[0].length -1);
}
public boolean searchRec2(int up,int left,int down,int right){
if (up < down || left > right){
return false;
}else if (target < matrix[up][left] || target > matrix[down][right]){
return false;
}
int mid = left + (right - left)/2;
int p = up;
while (p <= down && matrix[p][mid] <= target){
if (matrix[p][mid] == target){
return true;
}
p ++;
}
return searchRec(p,left,down,mid-1) || searchRec(up,mid+1,p-1,right);
}为运算符设计优先级
思路，是如果没有运算符就直接返回结果集，遍历找到运算符，将运算符分为左右两个部分进行组合
// 分治的办法给表达式设计优先级
public List<Integer> diffWaysToCompute(String input){
return partition(input);
}
public List<Integer> partition(String input){
List<Integer> result = new ArrayList<>();
if (!input.contains("+") && !input.contains("-") && !input.contains("*")){
result.add(Integer.parseInt(input));
return result;
}
for (int i=0;i<input.length();i++){
if (input.charAt(i) == "+" || input.charAt(i) == "-" || input.charAt(i) == "*"){
for (Integer left:partition(input.substring(0,i))){
for (Integer right:partition(input.substring(i+1))){
if (input.charAt(i) == "+"){
result.add(left + right);
}else if ((input.charAt(i) == "-")){
result.add(left - right);
}else {
result.add(left*right);
}
}
}
}
}
return result;
}给表达式添加运算符
// 主要思路是回溯时采用三种符号进行回溯添加
public List<String> addOperators(String num, int target) {
List<String> result = new ArrayList<>();
addOperators(num,target,0L,0L,"",result);
return result;
}
public void addOperators(String num, int target,Long lastOpera, Long curNum, String tempRes, List<String> result){
if (num.length() == 0 && curNum == target){
result.add(tempRes);
return;
}
// 回溯添加运算符
for (int i=1;i<=num.length();i++){
// 分割当前数和下一个数
// 分割当前数和下一个数
// 这里主要采用分治分割 0i 作为前一个数， i ~ 最后作为后一个数
String cur = num.substring(0,i);
// 进行剪枝
if (cur.length() > 1 && cur.charAt(0) == '0'){
return;
}
String next = num.substring(i);
// 已经有第一个数
if (tempRes.length() > 0){
// 尝试加
addOperators(next, target, Long.parseLong(cur),curNum + Long.parseLong(cur),tempRes + "+" + cur,result);
// 尝试减
addOperators(next,target,-Long.parseLong(cur),curNum - Long.parseLong(cur),tempRes + "-" + cur,result);
addOperators(next,target,lastOpera * Long.parseLong(cur),(curNum - lastOpera) + lastOpera * Long.parseLong(cur),tempRes + "*" + cur,result);
}else {
addOperators(next,target,Long.parseLong(cur),Long.parseLong(cur),cur,result);
}
}
}计算右侧小于当前元素个数
// 使用的是 倒叙依次插入，然后使用 二分查找 返回具体的插入位置
public List<Integer> countSmaller(int[] nums) {
List<Integer> list = new ArrayList<>();
if (nums == null || nums.length == 0){
return list;
}
int n = nums.length;
int[] counts = new int[n];
List<Integer> temp = new ArrayList<>();
for (int i=n-1;i>=0;i--){
int index = binarySearch(temp, nums[i]);
if (index < 0){
index = -(index+1);
}
System.out.println(index);
temp.add(index,nums[i]);
counts[i] = index;
}
for (int i=0;i<n;i++){
list.add(counts[i]);
}
return list;
}
public int binarySearch(List<Integer> list, int target){
int left = 0; int right = list.size();
while (left < right){
int mid = left + (right - left)/2;
if (list.get(mid) >= target){
right = mid;
}else {
left = mid + 1;
}
}
return left;
}// 使用 二茬搜索数计算右侧小于当前元素个数
向左插只统计向左插入的个数，向右插开始统计插入的位置，并使用全局变量返回
class BSTNode{
int val;
int count;
BSTNode left;
BSTNode right;
public BSTNode(int x){
this.val = x;
this.count = 0;
}
}
int count_small;
public BSTNode BST_insert(BSTNode root, BSTNode node){
// 往左插入代表，右边的数为0 ，但是其自身的数会 加
if (root.val >= node.val){
// 向左插入
root.count ++;
if (root.left != null){
root.left = BST_insert(root.left,node);
}else {
// 左子树为 null
root.left = node;
}
}else {
this.count_small += root.count + 1;
if (root.right != null){
root.right = BST_insert(root.right,node);
}else {
root.right = node;
}
}
return root;
}
public List<Integer> countSmaller2(int[] nums){
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0){
return result;
}
int n = nums.length;
BSTNode node = new BSTNode(nums[n-1]);
result.add(0,0);
for (int i=1;i<n;i++){
count_small = 0;
node = BST_insert(node, new BSTNode(nums[n - i - 1]));
result.add(0,count_small);
}
return result;
} private void mergeSort(int[] nums, int left, int right, int[] ind, Integer[] ans) {
if (left == right) {
return;
}
int mid = (left + right) / 2;
mergeSort(nums, left, mid, ind, ans);
mergeSort(nums, mid+1, right, ind, ans);
merge(nums, left, mid, right, ind, ans);
}
private void merge(int[] nums, int left, int mid, int right, int[] ind, Integer[] ans) {
int[] larr = Arrays.copyOfRange(nums, left, mid+1), rarr = Arrays.copyOfRange(nums, mid+1, right+1), preind = Arrays.copyOfRange(ind, left, right+1);
int i = 0, j = 0, k = left, cnt = 0, nl = larr.length, nr = rarr.length;
while (i < nl && j < nr) {
while (i < nl && j < nr && larr[i] <= rarr[j]) {
ans[preind[i]] += cnt;
ind[k] = preind[i];
nums[k++] = larr[i++];
}
while (i < nl && j < nr && rarr[j] < larr[i]) {
ind[k] = preind[j + nl];
nums[k++] = rarr[j++];
++cnt;
}
}
while (i < nl) {
ans[preind[i]] += cnt;
ind[k] = preind[i];
nums[k++] = larr[i++];
}
while (j < nr) {
ind[k] = preind[j + nl];
nums[k++] = rarr[j++];
}
}
public List<Integer> countSmaller4(int[] nums) {
int n = nums.length;
if (n == 0) {
return Collections.emptyList();
}
Integer[] ans = new Integer[n];
Arrays.fill(ans, 0);
int[] ind = new int[n];
for (int i=0; i<n; ++i) {
ind[i] = i;
}
mergeSort(nums, 0, n-1, ind, ans);
return new ArrayList<Integer>(Arrays.asList(ans));
}// 使用归并分治进行统计计算右侧小于当前元素的个数
思路是，当左边进行归并放入时，这是统计右边放入的个数，就是右边放入个数
- 创建临时数组，创建索引数组，创建统计数组，初始化索引数组
- 归并分割，l == r 进行回溯，分为两部分 l mid,mid +1 r 治，合并统计
- 复制索引数组，然后对索引数组进行排序，使用两个指针，指向 前半部分首位 和后半部分首位，在归并左部数字时，右部已经归并的就是在右边的统计量 当然在统计是采用 += 进行计算
public List<Integer> countSmaller3(int[] nums) {
List<Integer> res = new ArrayList<>();
int len = nums.length;
if (len == 0) {
return res;
}
temp = new int[len];
counter = new int[len];
indexes = new int[len];
// 保存一个索引数组，初始化索引数组
for (int i = 0; i < len; i++) {
indexes[i] = i;
}
mergeAndCountSmaller(nums, 0, len - 1);
for (int i = 0; i < len; i++) {
res.add(counter[i]);
}
return res;
}
private void mergeAndCountSmaller(int[] nums, int l, int r) {
if (l == r) {
// 数组只有一个元素的时候，没有比较，不统计
return;
}
int mid = l + (r - l) / 2;
mergeAndCountSmaller(nums, l, mid);
mergeAndCountSmaller(nums, mid + 1, r);
// 归并排序的优化，同样适用于该问题
// 如果索引数组有序，就没有必要再继续计算了
if (nums[indexes[mid]] > nums[indexes[mid + 1]]) {
mergeOfTwoSortedArrAndCountSmaller(nums, l, mid, r);
}
}
/**
* [l, mid] 是排好序的
* [mid + 1, r] 是排好序的
*
* @param nums
* @param l
* @param mid
* @param r
*/
private void mergeOfTwoSortedArrAndCountSmaller(int[] nums, int l, int mid, int r) {
// 3,4 1,2
for (int i = l; i <= r; i++) {
temp[i] = indexes[i];
}
// 前半部数组第一个元素
int i = l;
// 后半数组第一个元素
int j = mid + 1;
// 遍历整个数组
for (int k = l; k <= r; k++) {
// 左指针超过mid 但还没结束，说明后半部分还有，将j 赋值k j++
if (i > mid) {
indexes[k] = temp[j];
j++;
// j 大于 r 右半部分已经遍历完，但还没结束，说明左半部分还没遍历完，i赋值k i++; 当赋值左半部分要统计，
// 直接的右半部分，因为右边都已经出去，那么统计数， 整个右半部分
} else if (j > r) {
indexes[k] = temp[i];
i++;
// 此时 j 用完了，[7,8,9 | 1,2,3]
// 之前的数就和后面的区间长度构成逆序
counter[indexes[k]] += (r - mid);
// 都没都终端 如果左 小于右 ，统计 右边已经出的
} else if (nums[temp[i]] <= nums[temp[j]]) {
indexes[k] = temp[i];
i++;
// 此时 [4,5, 6 | 1,2,3 10 12 13]
// mid j
counter[indexes[k]] += (j - mid - 1);
// 右边进行交换
} else {
// nums[indexes[i]] > nums[indexes[j]] 构成逆序
indexes[k] = temp[j];
j++;
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录