您現在的位置: 365建站網 > 365學習 > 數組小和(單調和)

數組小和(單調和)

文章來源:365jz.com     點擊數:196    更新時間:2017-11-24 11:29   參與評論

數組小和的定義如下:例如,數組s=[1,3,5,2,4,6]
在s[0]的左邊小于或等于s[0]的數的和為0
在s[1]的左邊小于或等于s[1]的數的和為1
在s[2]的左邊小于或等于s[2]的數的和為1+3=4
在s[3]的左邊小于或等于s[3]的數的和為1
在s[4]的左邊小于或等于s[4]的數的和為1+3+2=6
在s[5]的左邊小于或等于s[5]的數的和為1+3+5+2+4=15
所以s的小和為0+1+4+1+6+15=27
給定一個數組s,實現函數返回s的小和。

對于本題,最容易想到的就是通過二重循環暴力求解,時間復雜度O(n^2),代碼如下:

public class ArraySmallSum {

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 2, 4, 6};
        int smallSum = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    smallSum += arr[j];
                }
            }
        }
        System.out.println(smallSum);
    }
}

這樣的時間復雜度顯然是不能令人滿意的,這里我們利用歸并排序,在對有序子數組進行merge的同時,累加數組小和,時間復雜度O(nlogn),代碼如下:

public class ArraySmallSum {

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


    public static int getSmallSum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return mergeSortRecursion(arr, 0, arr.length - 1);
    }

    /**
     * 遞歸實現歸并排序
     *
     * @param arr
     * @param l
     * @param r
     * @return 返回數組小和
     */
    public static int mergeSortRecursion(int[] arr, int l, int r) {
        if (l == r) {   // 當待排序數組長度為1時,遞歸開始回溯,進行merge操作
            return 0;
        }
        int mid = (l + r) / 2;
        return mergeSortRecursion(arr, l, mid) + mergeSortRecursion(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    /**
     * 合并兩個已排好序的數組s[left...mid]和s[mid+1...right]
     *
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @return 返回合并過程中累加的數組小和
     */
    public static int merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];    // 輔助存儲空間 O(n)
        int index = 0;
        int i = left;
        int j = mid + 1;
        int smallSum = 0;       // 新增,用來累加數組小和
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                // 當前一個數組元素小于或等于后一個數組元素時,累加小和
                // s[i] <= s[j] -> s[i] <= s[j]...s[right]
                smallSum += arr[i] * (right - j + 1);
                temp[index++] = arr[i++];
            } else {
                temp[index++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[index++] = arr[i++];
        }
        while (j <= right) {
            temp[index++] = arr[j++];
        }
        for (int k = 0; k < temp.length; k++) {
            arr[left++] = temp[k];
        }
        return smallSum;
    }
}

??途W有道數組單調和,實際上和該題為同一道題。
另一道數組中的逆序對,與該題解法類似,只是merge時逆序對的累加條件和算法有所不同,此時merge操作的代碼如下:

/**
* 合并兩個已排好序的數組s[left...mid]和s[mid+1...right]
*
* @param arr
* @param left
* @param mid
* @param right
* @return 返回合并過程中累加逆序對
*/
public static int merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];    // 輔助存儲空間 O(n)
    int index = 0;
    int i = left;
    int j = mid + 1;
    int inverseNum = 0;       // 新增,用來累加數組逆序對
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[index++] = arr[i++];
        } else {
            // 當前一個數組元素大于后一個數組元素時,累加逆序對
            // s[i] > s[j] -> s[i]...s[mid] > s[j]
            inverseNum += (mid - i + 1);
            temp[index++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[index++] = arr[i++];
    }
    while (j <= right) {
        temp[index++] = arr[j++];
    }
    for (int k = 0; k < temp.length; k++) {
        arr[left++] = temp[k];
    }
    return inverseNum;
}

如對本文有疑問,請提交到交流論壇,廣大熱心網友會為你解答??! 點擊進入論壇


發表評論 (196人查看,0條評論)
請自覺遵守互聯網相關的政策法規,嚴禁發布色情、暴力、反動的言論。
用戶名: 驗證碼: 點擊我更換圖片
最新評論
------分隔線----------------------------
自拍偷拍福力视频,偷拍国际精品,麻豆一区福利电影,国产网红视频午夜福利,se视频大全,久久国产AV影院 男朋友把我腿打开了| 雨后小故事| 人妻办公室被强奷| 民间偷实拍野战视频| 800av凹凸视频在线观看| 小乌酱黑白双丝交足在线看| 中国女人soxo9uentetv| 50岁丰满女人裸体毛茸茸| 神马影院在线观看在线观看看| 日本高清色在线视频免费| xxxx中国高潮喷水| 人妻无码av中文系列久久免费| 九九厕所偷拍精品视频| 男同志网站| chinses中国女人china| 无翼鸟漫画| 日本另类潮喷video| 国产高清精品福利私拍国产写真| 亚洲成av人片在线观看无| 日本亚州视频在线八a| 任你爽任你鲁在线视频| 欧美乱做18vivode| 国产日韩av免费无码一区二区| 欧美真人性做爰高清大片| 岛国在线无码高清视频| 国产毛片不卡野外视频| 人妻无码不卡中文字幕系列| 老司机在线精品视频播放| 裸体男同gay自慰| 国产老妇伦国产熟女老妇高清| 无码黄动漫在线观看| http://www.icomfin.com