算法-小和问题（归并思路，O(N*logN)）

2022-3-29 diaba 算法 

package com.jiucaiyuan.net.question;

/**
 * <pre>
 * 一个数组arr的小和=所有位置上的值，左侧比概述小的和，就是该数组的小和
 * 本示例是解法2
 *
 * 解法1.暴力解题，循环处理所有数组的数，找到左侧比所处理的数小的加入结果和中
 *      时间复杂度O(N^2)
 *
 * 解法2.转化为循环数组所有数，找出右侧比他大，即产生当前数加入到小和中
 *      求右边比arr[i]大，可以转化为归并思路处理
 *      划分左右两个进行排序，然后merge，在merge过程中，如果右侧比左侧大，则累计小和，否则直接合并，最后的累计值即是小和
 *   时间复杂度O(N*logN)
 * </pre>
 *
 * @Author jiucaiyuan  2022/3/29 22:57
 * @mail services@jiucaiyuan.net
 */

public class SmallSum {

    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    public static int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    /*
     * 合并arr[l,mid] 和 arr[mid+1,r] 两个数组
     */
    private static int merge(int[] arr, int l, int mid, int r) {
        int sum = 0;
        //合并后的数组
        int[] temp = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        //两个数组都有数时
        while (p1 <= mid && p2 <= r) {
            //相等不计算小和
            if (arr[p1] < arr[p2]) {
                sum += arr[p1] * (r - p2 + 1);
                temp[i++] = arr[p1++];
            } else {
                temp[i++] = arr[p2++];
            }
        }
        //前半段数组长
        while (p1 <= mid) {
            temp[i++] = arr[p1++];
        }
        //后半段数组长
        while (p2 <= r) {
            temp[i++] = arr[p2++];
        }
        //把合并后的temp数组复制到arr中
        for (int index = 0; index < temp.length; index++) {
            arr[l + index] = temp[index];
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 2, 5, 1};
        System.out.println(smallSum(arr));
    }
}

« 算法-逆序对（归并思路） | 算法-43.字符串相乘»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022