weixin_42042460
2018-04-24 14:07
采纳率: 63.6%
浏览 1.4k
已采纳

一个关于分治算法的问题

比如有一个List L = [(0,1), (1, 0), (0, 1), (1, 1), (1, 2), (3, 1), (3, 1), (2, 2), (2, 3), (3, 2), (2, 3), (4, 3), (3, 4), (4, 4), (4, 5), (5, 5)]

包含N对两两一起的Integer

现在有 (ai,bi)∈L 和 (aj,bj)∈L

我们假设如果任意两对满足以下**三种情况其一**,就称这两组数是一对
ai=aj 并且 bi=bj
ai<aj
bi<bj
比如 (1,2) (1,1)就不是一对,因为任意一个条件都不满足

那么假设我们有一组中间的(ai,bi),在满足什么情况下我们可以直接停止搜索他的对子呢?

另外用**分治法**的话,给出一组数字,如何寻找他的一对数组呢?

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • devmiao 2018-04-24 14:37
    已采纳
     package com.test;  
    
    import java.util.ArrayList;  
    import java.util.List;  
    
    public class MyTest02 {  
        public static void main(String[] args) {  
            int[] a = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };  
            int[] s = getMaxSummary(a, 0, 15);  
            for (int i = 0; i < s.length; i++) {  
                System.out.println(s[i]);  
            }  
        }  
    
        /** 
         * 程序主入口 
         * @param A 
         * @param low 
         * @param high 
         * @return 
         */  
        public static int[] getMaxSummary(int[] A, int low, int high) {  
            if (low == high) { // 如果長度就一個,那麼就把這個取出來  
                int[] result = { low, high, A[low] };  
                return result;  
            } else {  
                int middle = (int) Math.floor((low + high) / 2); // 获取中间值  
                int[] left = new int[3]; // 保存左边部分返回结果  
                int[] right = new int[3]; // 保存右边部分返回结果  
                int[] cross = new int[3]; // 返回交叉部分返回结果  
                left = getMaxSummary(A, low, middle);  
                right = getMaxSummary(A, middle + 1, high);  
                cross = getMaxCrossMid(A, low, high, middle);  
                if (left[2] >= right[2] && left[2] >= cross[2]) {   // 那部分大就用了那部分  
                    return left;  
                } else if (right[2] >= left[2] && right[2] >= cross[2]) {  
                    return right;  
                } else {  
                    return cross;  
                }  
            }  
        }  
    
        /** 
         * 獲取最大子數組(一部分在左邊,一部分在右邊) 
         *  
         * @param A 
         * @param low 
         * @param high 
         * @param middle 
         * @return 
         */  
        public static int[] getMaxCrossMid(int[] A, int low, int high, int middle) {  
            int leftSum = Integer.MIN_VALUE;  
            int sum = 0; // 保存和的  
            int left = 0; // 记录左边位置  
            for (int i = middle; i >= low; i--) {  
                sum = sum + A[i];  
                if (sum > leftSum) { // 证明所加数字为正数,那么符合条件(因为最大子数组内正数越多指定越大)  
                    leftSum = sum;  
                    left = i;  
                }  
            }  
    
            int rightSum = Integer.MIN_VALUE;  
            int sum2 = 0;  
            int right = 0; // 记录右边位置  
            for (int i = middle + 1; i <= high; i++) {  
                sum2 = sum2 + A[i];  
                if (sum2 > rightSum) {  
                    rightSum = sum2;  
                    right = i;  
                }  
            }  
    
            int[] result = new int[3];  
            result[0] = left;  
            result[1] = right;  
            result[2] = leftSum + rightSum;  
            return result;  
        }  
    
    
    
    
    }
    
    已采纳该答案
    打赏 评论
  • devmiao 2018-04-24 14:37

    算法实现的思路
    FIND-MAXIMUM-SUBARRAY(A,low,high)

    if high==low

    return (low,high,A[low])

    else

    mid= ⌊(low+high)/2⌋

    (left_low,left_high,left_sum)=FIND-MAXIMUM-SUBARRAY(A,low,mid)

    (right_low,right_high,right_sum)=FIND-MAXIMUM-SUBARRAY(A,mid+1,high)

    (cross_low,cross_high,cross_sum)=FIND-MAXIMUM-SUBARRAY(A,low,mid,high)

    if left_sum>=right_sum and left_sum>=cross_sum

    return (left_low,left_high,left_sum)

    elseif right_sum>=left_sum and right_sum>=cross_sum

    return (right_low,right_high,right_sum)

    else

    return (cross_low,cross_high,cross_sum)

    打赏 评论

相关推荐 更多相似问题