算法分析——分治

1、分治算法

1.1 基本概念

在計算機科學中，分治法是建構基于多項分支遞歸的一種很重要的算法範式。字面上的解釋是「分而治之」，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎，如排序算法（快速排序、歸并排序）、傅立葉變換（快速傅立葉變換）。

1.2 分治法适用情況

（1）該問題的規模縮小到一定的程度就可以容易地解決；

（2）該問題可以分解為若幹個規模較小的相同問題，即該問題具有最優子結構性質；

（3）利用該問題分解出的子問題的解可以合并為該問題的解；

（4）該問題所分解出的各個子問題是互相獨立的，即子問題之間不包含公共的子子問題；

其中第三條是關鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動态規劃。

第四條涉及到分治法的效率，如果各子問題是不獨立的則分治法要做許多不必要的工作，重複地解公共的子問題，此時雖然可用分治法，但一般用動态規劃法較好（可以參考下面第三個題目）。

1.3 分治法一般步驟

• Step1 : 将原問題分解為若幹個規模較小，互相獨立，與原問題形式相同的子問題；
• Step2 : 若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題;
• Step3 : 将各個子問題的解合并為原問題的解;

2、Leetcode題目

2.1 Leetcode169 : 多數元素

題目描述：給定一個大小為 n 的數組，找到其中的多數元素。多數元素是指在數組中出現次數大于 ⌊ n/2 ⌋ 的元素。

你可以假設數組是非空的，并且給定的數組總是存在多數元素。

示例1：

輸入: [3,2,3]

輸出: 3

示例2：

輸入: [2,2,1,1,1,2,2]

輸出: 2

題目分析：這道題還是比較簡單的，有很多種解法。比如，方法一：由于衆數出現的頻率大于n/2,是以在排序之後衆數必存在于下标[n/2]處。是以可以将原數組排序，然後輸出位于

n/2

位置的數，該數即為衆數。方法二：哈希表，通過使用哈希映射得到每個值出現的次數。但是我們需要用分治的方法去求解這個問題。

我們直到如果數

a

是數組

nums

的衆數，如果我們将

nums

分成兩部分，那麼

a

必定是至少一部分的衆數。這樣以來，我們就可以使用分治法解決這個問題：将數組分成左右兩部分，分别求出左半部分的衆數 a1 以及右半部分的衆數 a2，随後在 a1 和 a2 中選出正确的衆數。

代碼：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        return majorityElementRec(nums, 0, nums.size() - 1);
    }

    int count(vector<int>& nums, int target, int low, int height) {
        int c = 0;
        for (int i = low; i <= height; ++i)
            if (nums[i] == target)
                c++;
        return c;
    }

    int majorityElementRec(vector<int>& nums, int low, int height) {
        if (low == height)
            return nums[low];
        int mid = low + (height - low) / 2;

        int left = majorityElementRec(nums, low, mid);
        int right = majorityElementRec(nums, mid + 1, height);
        
        //計算區間内的衆數，傳回
        if (count(nums, left, low, height) > (height - low + 1) / 2)
            return left;
        if (count(nums, right, low, height) > (height - low + 1) / 2)
            return right;
        return -1;
    }
};
           

2.2 Leetcode53 : 最大子序和

題目描述：給定一個整數數組

nums

，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例：

輸入: [-2,1,-3,4,-1,2,1,-5,4]

輸出: 6

解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。

題目分析：

代碼：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
    	return maxSub(nums, 0, nums.size()-1);
    }

    int maxSub(std::vector<int>& Array, int low, int height){
    	if(height == low){
    		//隻有一個元素是，傳回值
    		return Array[low];
    	}

		int mid = low + (height - low) / 2;
		int left = maxSub(Array, low, mid);
		int right = maxSub(Array, mid+1, height);

		//左邊子數組，從右往左計算
		int leftMaxValue = Array[mid];
		int temp = 0;

		for(int i = mid; i >= low; i--){
			temp += Array[i];
			leftMaxValue = max(temp, leftMaxValue);
		}

		//右邊子數組，從左往右計算
		int rightMaxValue = Array[mid+1];
		temp = 0;

		for(int j = mid+1; j <= height; j++){
			temp += Array[j];
			rightMaxValue = max(temp, rightMaxValue);
		}
        int value = max(left, right);
		return max(value, rightMaxValue+leftMaxValue);
    }
};
           

2.3 Leetcode50 : pow(x, n)

題目描述：實作 pow(x, n) ，即計算 x 的 n 次幂函數。

示例1：

輸入: 2.00000, 10

輸出: 1024.00000

示例2：

輸入: 2.00000, -2

輸出: 0.25000

解釋: 2-2 = 1/22 = 1/4 = 0.25

題目分析：

代碼：

class Solution {
public:
    double myPow(double x, int n) {
    	if(n == 0){
    		return 1;
    	}else if(n > 0){
            return multiplyDivide(x, 0, n-1);
    	}else{
         	//int型最大值為2147483647。此處不能再用abs(n)
            if(n == -2147483648)
                return multiplyDivide(1/x, 0, 2147483647);
            return multiplyDivide(1/x, 0, abs(n)-1);
    	}
    }

    double multiplyDivide(double value, int low, int height){
    	if(height == low){
    		return value;
    	}

    	int mid = low + (height - low) / 2;
    	double left = multiplyDivide(value, low, mid);

        //注意，是以左右兩邊的值都是相同的，在歸并的時候差别僅在于當n為奇數的時候，左右兩邊需要歸并的value個數相差為1。
        //是以直接将左邊歸并的值給右邊即可，不需要再重複計算。
    	double right;
    	if(height % 2 == 0){
    		right = left / value;
    	}else{
    		right = left;
    	}

    	//double right = multiplyDivide(value, mid+1, height);

    	return left * right;
    }
};