Tag Archives: 分治法

HDOJ 1007-Quoit Design

HDOJ 1007-Quoit Design

Quoit Design

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 77740    Accepted Submission(s): 20729

Problem DescriptionHave you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.

Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.

InputThe input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.

OutputFor each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.

Sample Input

2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0

Sample Output

0.71
0.00
0.75

AuthorCHEN, Yue 
SourceZJCPC2004
RecommendJGShining   |   We have carefully selected several similar problems for you:  10061009100510081004


给定二维平面上的N个点,问其中距离最近的两个点的距离是多少,输出最短距离的一半。

典型的平面上最近点对问题。大学算法课上有,采用分治法。即首先把所有点按x排序,然后取x轴中点m,把所有点划分为左右两半L和R,在L和R中递归求最近点对的距离,假设为dL和dR。假设d=min(dL,dR)。则还需要判断最近点对是否会在中点m附近,假设存在这种情况,则跨越m的最近点对必须满足距离m小于d。把这部分点收集起来,按y排序,然后求任意两点之间的距离,期间可以break加速。

完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

struct Point
{
	double x_, y_;
	Point() :x_(0), y_(0) {};
	Point(double x, double y) :x_(x), y_(y) {};
};

bool CmpX(const Point &p1, const Point &p2) {
	return p1.x_ < p2.x_;
}

bool CmpY(const Point &p1, const Point &p2) {
	return p1.y_ < p2.y_;
}

// 暂时只算距离平方,最后开平方根
double CalDist(const Point &p1, const Point &p2) {
	return (p1.x_ - p2.x_)*(p1.x_ - p2.x_) + (p1.y_ - p2.y_)*(p1.y_ - p2.y_);
}

double CalMinDist(vector<Point> &data, int l, int r) {

	if (r - l == 2) {
		return CalDist(data[l], data[l + 1]);
	}
	else if (r - l == 3) {
		double d1 = CalDist(data[l], data[l + 1]);
		double d2 = CalDist(data[l], data[l + 2]);
		double d3 = CalDist(data[l + 1], data[l + 2]);
		return min(min(d1, d2), d3);
	}

	int m = l + (r - l) / 2;
	int mx = data[m].x_;
	double dd = min(CalMinDist(data, l, m), CalMinDist(data, m, r));
	double d = sqrt(dd);

	vector<Point> rect;
	for (int i = l; i < r; ++i) {
		if (data[i].x_ > mx - d && data[i].x_ < mx + d) {
			rect.push_back(data[i]);
		}
	}

	sort(rect.begin(), rect.end(), CmpY);
	for (int i = 0; i < rect.size(); ++i) {
		for (int j = i + 1; j < rect.size(); ++j) {
			double tmpd = CalDist(rect[i], rect[j]);
			if (tmpd > dd)break;
			dd = min(dd, tmpd);
		}
	}

	return dd;
}

int main() {
	freopen("input.txt", "r", stdin);

	int n;
	while (scanf("%d", &n)) {
		if (n == 0)break;
		vector<Point> data(n, Point());
		for (int i = 0; i < n; ++i) {
			scanf("%lf %lf", &data[i].x_, &data[i].y_);
		}
		sort(data.begin(), data.end(), CmpX);
		printf("%.2lf\n", sqrt(CalMinDist(data, 0, data.size())) / 2);
	}

	return 0;
}

本代码提交AC,用时982MS。

参考: https://www.cnblogs.com/MartinLwx/p/9757828.htmlhttps://www.jianshu.com/p/8bc681afbaff

剑指 Offer 04. 二维数组中的查找

剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下:

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5,返回 true。

给定 target = 20,返回 false。

限制:

0 <= n <= 1000

0 <= m <= 1000

注意:本题与主站 240 题相同:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一个矩阵,每行从左到右升序排列,每列从上到下升序排列,给定一个数,问这个数在不在矩阵中。

从矩阵右上角开始查找,代码如下:

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        int n = matrix.size(), m = matrix[0].size();
        int i = 0, j = m - 1;
        while(i < n && j >= 0) {
            if(matrix[i][j] == target) return true;
            if(target > matrix[i][j]) ++i;
            else --j;
        }
        return false;
    }
};

本代码提交AC,用时64MS。

LeetCode Range Sum Query – Mutable

LeetCode Range Sum Query – Mutable Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. The update(i, val) function modifies nums by updating the element at index i to val. Example:

Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

给定一个一维数组,要求实现范围求和,即求[i,j]之间的元素的和。sumRange(i,j)求i~j的元素和,update(i,val)更新下标为i的元素值为val。 第一敏感使用线段树,很久之前在hihoCoder上遇到过。 建树的方法是类似于树的后序遍历,即左右根。不断把[start,end]二分,构建左右子树,然后构建当前节点,当前节点的sum等于左右子树的sum的和。在递归的时候,递归到start==end时,说明只有一个元素了,此时sum就等于该元素。 查询的方法和建树方法类似,判断区间[i,j]和区间[start,end]的关系,假设start和end的中点是mid,如果j<=mid,递归在左子树查询;如果i>mid,递归在右子树查询;否则在[i,mid]和[mid+1,j]查询然后求和。 更新的方法和查询的方法类似,也是不断判断i和mid的关系,在左子树或者右子树递归更新,当找到该叶子节点时,更新它的sum,返回父节点也更新sum等于新的左右子树的sum的和。 完整代码如下: [cpp] class NumArray { private: struct Node { int start, end, sum; Node *left, *right; Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {}; }; Node *root; Node* constructTree(vector<int> &nums, int start, int end) { Node* node = new Node(start, end); if (start == end) { node->sum = nums[start]; return node; } int mid = start + (end – start) / 2; node->left = constructTree(nums, start, mid); node->right = constructTree(nums, mid + 1, end); node->sum = node->left->sum + node->right->sum; return node; } int sumRange(int i, int j, Node *root) { if (root == NULL)return 0; if (i == root->start&&j == root->end)return root->sum; int mid = root->start + (root->end – root->start) / 2; if (j <= mid)return sumRange(i, j, root->left); else if (i > mid)return sumRange(i, j, root->right); else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right); } void update(int i, int val, Node *root) { if (root->start == root->end && root->start == i) { root->sum = val; return; } int mid = root->start + (root->end – root->start) / 2; if (i <= mid)update(i, val, root->left); else update(i, val, root->right); root->sum = root->left->sum + root->right->sum; } public: NumArray(vector<int> nums) { root = NULL; if (!nums.empty())root = constructTree(nums, 0, nums.size() – 1); } void update(int i, int val) { if (root == NULL)return; update(i, val, root); } int sumRange(int i, int j) { if (root == NULL)return 0; return sumRange(i, j, root); } }; [/cpp] 本代码提交AC,用时172MS。]]>

LeetCode Different Ways to Add Parentheses

241. Different Ways to Add Parentheses241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +- and *.

Example 1:

Input: "2-1-1"
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

Input: "2*3-4*5" Output: [-34, -14, -10, -10, 10] Explanation:  (2*(3-(4*5))) = -34  ((2*3)-(4*5)) = -14  ((2*(3-4))*5) = -10  (2*((3-4)*5)) = -10  (((2*3)-4)*5) = 10241. Different Ways to Add Parentheses

给定一个包含+-*的运算字符串,求所有加括号的方案计算到的值。
采用分治法的思路,尝试在每个操作符分成两个部分,这就相当于分别把操作符左右两边括起来单独计算。然后left和right分开进行递归,最后merge。递归的终止条件是当字符串中不包含操作符时,直接返回这个字符串对应的数值。
分治法很经典的例子。
代码如下:

class Solution {
private:
    int operate(int a, int b, char c)
    {
        switch (c) {
        case ‘+’:
            return a + b;
        case ‘-‘:
            return a – b;
        case ‘*’:
            return a * b;
        }
    }
public:
    vector<int> diffWaysToCompute(string input)
    {
        int n = input.size();
        vector<int> ans;
        bool found = false;
        for (int i = 0; i < n; ++i) {
            if (input[i] == ‘+’ || input[i] == ‘-‘ || input[i] == ‘*’) {
                found = true;
                vector<int> lefts = diffWaysToCompute(input.substr(0, i));
                vector<int> rights = diffWaysToCompute(input.substr(i + 1));
                for (int j = 0; j < lefts.size(); ++j) {
                    for (int k = 0; k < rights.size(); ++k) {
                        ans.push_back(operate(lefts[j], rights[k], input[i]));
                    }
                }
            }
        }
        if (!found)
            return { atoi(input.c_str()) };
        return ans;
    }
};

本代码提交AC,用时3MS。

LeetCode Search a 2D Matrix II

240. Search a 2D Matrix II 240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false. 240. Search a 2D Matrix II


LeetCode Search a 2D Matrix基础上改动了一点点,但是难度增加不少。这一次,每行和每列都是递增的,但是这一行的行首元素和上一行的行末元素没有大小关系,这种矩阵有点像从左上角递增到右下角的一个曲面,想象一下。 一种比较笨的办法就是对每一行或者每一列二分搜索,复杂度为O(mlgn)或O(nlgm)。 参考这位大神的介绍,有很多厉害的算法,具体看原博客,这里简单给出其前两个算法的C++实现。 算法1相当于对角二分搜索,是线性复杂度的。搜索从矩阵右上角开始,遇到比当前元素大时,递增行;遇到比当前元素小时,递减列;直到找到相等元素,或者到达矩阵左下角。最坏情况是从右上角走到了左下角,复杂度为O(m+n)。 这种思路的代码如下:

class Solution {
public:
    bool searchMatrix(vector<vector<int> >& matrix, int target)
    {
        if (matrix.size() == 0)
            return false;
        int m = matrix.size(), n = matrix[0].size();
        if (n == 0)
            return false;
        int i = 0, j = n – 1;
        while (i < m && j >= 0) {
            while (i < m && matrix[i][j] < target)
                ++i;
            if (i >= m)
                return false;
            while (j >= 0 && matrix[i][j] > target)
                –j;
            if (j < 0)
                return false;
            if (matrix[i][j] == target)
                return true;
        }
        return false;
    }
};

本代码提交AC,用时129MS。
算法2利用了分治法的思路。每次取矩阵中心元素,把矩阵分成4个小份。如果target大于中心元素,则左上角部分可以全部舍弃掉,因为矩阵的行列都是递增的,左上角元素肯定全部小于中心元素,不必再找。此时可以递归的在剩余的3个小矩阵里查找。比如下图中心元素为9,如果要找26,则可以递归的在其右上角、左下角和右下角三个小矩阵中查找。

时间复杂度公式为T(n)=3T(n/2)+c,c为target和中心元素比较的时间。使用主方法可以算到T(n)=O(n1.58)。
分治法思路代码如下:

class Solution {
public:
    bool quadPart(vector<vector<int> >& matrix, int left, int top, int right, int bottom, int target)
    {
        if (left > right || top > bottom)
            return false;
        if (target < matrix[left][top] || target > matrix[right][bottom])
            return false;
        int midrow = left + (right - left) / 2, midcol = top + (bottom - top) / 2;
        if (target == matrix[midrow][midcol])
            return true;

        //if (target > matrix[midrow][midcol]) { // 抛弃左上角
        //	return quadPart(matrix, left, midcol + 1, midrow - 1, bottom, target) || // 右上角
        //		quadPart(matrix, midrow + 1, top, right, midcol - 1, target) || // 左下角
        //		quadPart(matrix, midrow, midcol, right, bottom, target); // 右下角
        //}
        //else {
        //	return quadPart(matrix, left, midcol + 1, midrow - 1, bottom, target) || // 右上角
        //		quadPart(matrix, midrow + 1, top, right, midcol - 1, target) || // 左下角
        //		quadPart(matrix, left, top, midrow, midcol, target); //左上角
        //}

        if (target > matrix[midrow][midcol]) { // 抛弃左上角
            return quadPart(matrix, left, midcol + 1, midrow, bottom, target) || // 右上角
                quadPart(matrix, midrow + 1, top, right, midcol, target) || // 左下角
                quadPart(matrix, midrow + 1, midcol + 1, right, bottom, target); // 右下角
        }
        else {
            return quadPart(matrix, left, midcol, midrow - 1, bottom, target) || // 右上角
                quadPart(matrix, midrow, top, right, midcol - 1, target) || // 左下角
                quadPart(matrix, left, top, midrow - 1, midcol - 1, target); //左上角
        }
    }
    bool searchMatrix(vector<vector<int> >& matrix, int target)
    {
        if (matrix.size() == 0)
            return false;
        int m = matrix.size(), n = matrix[0].size();
        if (n == 0)
            return false;
        return quadPart(matrix, 0, 0, m - 1, n - 1, target);
    }
};

本代码提交AC,用时168MS。
注意代码中注释掉的部分是错误代码,因为其在右下角或者左上角搜索时可能会进入死循环。比如要在上图搜索30,当搜索到右下角深色部分的小矩阵时,中心元素是17,本该搜索更小的矩阵30,但是根据注释代码中第一个if搜索右下角的代码,新的矩阵(右下角)的左上角坐标还是17,因为其坐标是(midrow, midcol),无论递归多少次,右下角的矩阵没有变小,所以进入了死循环。
正确的方法是把涉及到中点的两条边分配到不同的小矩阵里,必须使得每个小矩阵的左上角或右下角坐标有变化。

LeetCode Pow(x, n)

50. Pow(x, n)

Implement pow(xn), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−231, 231 − 1]

实现幂指数运算。 如果对x连乘n次,时间复杂度为$O(n)$,但使用分治法能降到$O(\log n)$。因为可以把$x^n$分解为: $\begin{equation*} x^n= \begin{cases} x^{\frac{n}{2}} \cdot x^{\frac{n}{2}}, & \text{if } n \text{ even}\\ x^{\frac{n-1}{2}} \cdot x^{\frac{n-1}{2}} \cdot x, & \text{if } n \text{ odd} \end{cases} \end{equation*}$

完整代码如下:

class Solution {
public:
    double doPow(double x, int n)
    {
        if (n == 0)
            return 1.0;
        double v = doPow(x, n / 2);
        if (n % 2 == 0)
            return v * v;
        else
            return v * v * x;
    }
    double myPow(double x, int n)
    {
        int m = n > 0 ? n : -n;
        double ans = doPow(x, m);
        return n > 0 ? ans : 1.0 / ans;
    }
};

本代码提交AC,用时3MS。
注意在子程序中不要调用两次doPow(x, n/2),算出一个v,然后直接v*v即可。

二刷。使用非递归的方法实现快速幂,代码如下:

class Solution {
public:
    double myPow(double x, int n)
    {
        if (n == 0)
            return 1;
        if (n == 1)
            return x;
        long long m = n; // 先转换为ll,否则n=INT_MIN是有问题
        m = m > 0 ? m : -m;
        double ans = 1;
        while (m) {
            if (m & 1)
                ans *= x;
            m >>= 1;
            x = x * x;
        }
        return n > 0 ? ans : 1 / ans;
    }
};

本代码提交AC,用时3MS。

三刷。注意n=INT_MIN时,第一种解法会有问题,需要用long long存储,代码如下:

class Solution {
public:
	double myPow2(double x, long long m) {
		if (x == 0.0)return 0.0;
		if (x == 1.0 || m == 0)return 1.0;
		if (m == 1)return x;
		if (m < 0) return 1.0 / myPow2(x, -m);

		if (m % 2 == 1)return x * myPow2(x*x, m >> 1);
		else return myPow2(x*x, m >> 1);
	}
	double myPow(double x, int n) {
		return myPow2(x, n);
	}
};

本代码提交AC,用时0MS。

LeetCode Maximum Subarray

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.


求最大连续子数组和,这是一道非常经典的题目,从本科时候就开始做了。有两种解法。

动态规划法

用dp数组存储到当前元素的最大子数组和,如dp[i-1]表示包含第i-1个元素的最大子数组和,则dp[i]表示包含第i个元素的最大子数组和。如果dp[i-1]>0,则dp[i]=dp[i-1]+nums[i];否则dp[i]=nums[i]。完整代码如下:

class Solution {
public:
    int maxSubArray(vector<int>& nums)
    {
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int ans = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (dp[i – 1] > 0)
                dp[i] = dp[i – 1] + nums[i];
            else
                dp[i] = nums[i];
            if (dp[i] > ans)
                ans = dp[i];
        }
        return ans;
    }
};

本代码只用扫描一遍数组,所以时间复杂度为$O(n)$。本代码提交AC,用时12MS。

分治法

将数组一分为二,比如数组[a,b]分为[a,m-1]和[m+1,b],递归求解[a,m-1]和[m+1,b]的最大连续子数组和lmax和rmax,但是[a,b]的最大连续子数组和还可能是跨过中点m的,所以还应该从m往前和往后求一个包含m的最大连续子数组和mmax,然后再求lmax,rmax,mmax的最大值。完整代码如下:

class Solution {
public:
    int divide(vector<int>& nums, int left, int right)
    {
        if (left == right)
            return nums[left];
        if (left == right – 1)
            return max(nums[left] + nums[right], max(nums[left], nums[right]));
        int mid = (left + right) / 2;
        int lmax = divide(nums, left, mid – 1);
        int rmax = divide(nums, mid + 1, right);
        int mmax = nums[mid], tmp = nums[mid];
        for (int i = mid – 1; i >= left; i–) {
            tmp += nums[i];
            if (tmp > mmax)
                mmax = tmp;
        }
        tmp = mmax;
        for (int i = mid + 1; i <= right; i++) {
            tmp += nums[i];
            if (tmp > mmax)
                mmax = tmp;
        }
        return max(mmax, max(lmax, rmax));
    }
    int maxSubArray(vector<int>& nums) { return divide(nums, 0, nums.size() – 1); }
};

本代码可以类比平面上求最近点对的例子,需要考虑跨界的问题,时间复杂度为$O(nlgn)$。本代码提交AC,用时也是12MS。

综合来看,还是动态规划法更漂亮。

二刷。动态规划还可以再简化,即不用额外的DP数组,代码如下:

class Solution {
public:
	int maxSubArray(vector<int>& nums) {
		int n = nums.size();
		int max_sum = INT_MIN, cur_sum = 0;
		for (int i = 0; i < n; ++i) {
			if (cur_sum >= 0) {
				cur_sum += nums[i];
			}
			else {
				cur_sum = nums[i];
			}
			max_sum = max(max_sum, cur_sum);
		}
		return max_sum;
	}
};

本代码提交AC,用时4MS,击败98%用户。

LeetCode Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

这道题很有意思,虽然本科的时候就做过练习题,用二分查找递归的减少数据规模,但是当时只写过伪代码,这次真正写代码提交的时候,发现有很多BUG。

这个题的思路有3种:1)两个数组放一起排序,取中位数O((m+n)lg(m+n));2)用归并排序的方式把他们Merge到一块,取中间数O(m+n),其实边Merge边数数,Merge到(m+n)/2个数的时候就已经是中位数了;3)二分的思路,比较A,B数组的中位数,根据大小关系选择在前半段或后半段继续递归。
我开始尝试了二分的思路,很多测试样例不能通过,要考虑奇偶性等问题也导致代码不够优雅。查看网络发现可以把这一题转换为从两个已排序数组A,B中取第k小的元素的问题,如果是m+n是奇数,则取中间那个数,偶数则取中间两个数求平均。

关于从两个已排序数组A,B中取第k小的元素的问题,这篇文章有较详细的讨论

下面简要讲一下最后一种O(lgm+lgn)的方法。

如果A的某个元素$A_i$和B的某两个连续元素$B_j$和$B_{j-1}$有关系$B_{j-1}\leq A_i\leq B_j$,那么可以确定$A_i$就是AB合起来的第$i+j+1$小的元素,因为$A_i$大于A中前$i$个元素,$A_i$又大于$B_{j-1}$,而$B_{j-1}$又大于B前面$j-1$个元素,所以在AB合起来的数组中,$A_i$大于A前面$i$个元素和B前面$j$个元素,排在第$i+j+1$的位置。同理如果$A_{i-1}\leq B_j\leq A_i$,则$B_j$是第$i+j+1$小的元素。
如果我们令$k=i+j+1$,则可以容易得到第$k$小的元素。关于i,j的取值问题,理论上i,j可以取任意值,只要满足$i+j=k-1$就可以了。不过常见的取法是先取$i$为A的中点,然后取$j=k-1-i$;或者按A,B元素个数的比例取值,比如上述链接中的代码。

上述链接中给出了如果A,B中不存在相同元素时的代码,如下:

int findKthSmallest(int A[], int m, int B[], int n, int k)
{
    assert(m >= 0);
    assert(n >= 0);
    assert(k > 0);
    assert(k <= m + n);
    int i = (int)((double)m / (m + n) * (k – 1));
    int j = (k – 1) – i;
    assert(i >= 0);
    assert(j >= 0);
    assert(i <= m);
    assert(j <= n); // invariant: i + j = k-1 // Note: A[-1] = -INF and A[m] = +INF to maintain invariant
    int Ai_1 = ((i == 0) ? INT_MIN : A[i – 1]);
    int Bj_1 = ((j == 0) ? INT_MIN : B[j – 1]);
    int Ai = ((i == m) ? INT_MAX : A[i]);
    int Bj = ((j == n) ? INT_MAX : B[j]);
    if (Bj_1 < Ai && Ai < Bj)
        return Ai;
    else if (Ai_1 < Bj && Bj < Ai)
        return Bj;
    assert((Ai > Bj && Ai_1 > Bj) || (Ai < Bj && Ai < Bj_1)); // if none of the cases above, then it is either:
    if (Ai < Bj) // exclude Ai and below portion // exclude Bj and above portion
        return findKthSmallest(A + i + 1, m – i – 1, B, j, k – i – 1);
    else /* Bj < Ai */ // exclude Ai and above portion // exclude Bj and below portion
        return findKthSmallest(A, i, B + j + 1, n – j – 1, k – j – 1);
}

针对本题C++代码如下:

class Solution {
public:
    double findKthSmallest(vector<int>& nums1, vector<int>& nums2, int k) //find kth smallest
    {
        int m = nums1.size(), n = nums2.size(); //always assume that m is equal or smaller than n
        if (m > n)
            return findKthSmallest(nums2, nums1, k);
        if (m == 0)
            return nums2[k – 1];
        if (k == 1)
            return min(nums1[0], nums2[0]); //divide k into two parts
        int i = (int)((double)m / (m + n) * (k – 1));
        int j = (k – 1) – i;
        int Ai_1 = ((i == 0) ? INT_MIN : nums1[i – 1]);
        int Bj_1 = ((j == 0) ? INT_MIN : nums2[j – 1]);
        int Ai = ((i == m) ? INT_MAX : nums1[i]);
        int Bj = ((j == n) ? INT_MAX : nums2[j]);
        if (Bj_1 < Ai && Ai < Bj)
            return Ai;
        else if (Ai_1 < Bj && Bj < Ai)
            return Bj;
        if (Ai < Bj) {
            vector<int> v1(nums1.begin() + i + 1, nums1.end());
            vector<int> v2(nums2.begin(), nums2.begin() + j);
            return findKthSmallest(v1, v2, k – i – 1);
        }
        else if (Ai > Bj) {
            vector<int> v1(nums1.begin(), nums1.begin() + i);
            vector<int> v2(nums2.begin() + j + 1, nums2.end());
            return findKthSmallest(v1, v2, k – j – 1);
        }
        else
            return Ai;
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        int total = nums1.size() + nums2.size();
        if (total & 0x01)
            return findKthSmallest(nums1, nums2, total / 2 + 1);
        else
            return (findKthSmallest(nums1, nums2, total / 2) + findKthSmallest(nums1, nums2, total / 2 + 1)) / 2;
    }
};

本代码提交AC,用时52MS。

二刷。
上面的解法真的太复杂了,完全记不住。从两个有序数组中求第K大的数,在http://www.geeksforgeeks.org/k-th-element-two-sorted-arrays/有非常详细的解法,归并O(m+n)的解法就不说了。
O(lgn+lgm)的解法。假设arr1和arr2的中位数分别是arr1[mid1]和arr2[mid2],如果mid1+mid2<k,说明两个中位数的位置都太小了,第k大的数比较大。如果arr1[mid1]<arr2[mid2],则mid1左边是这四块中最小的一块,k肯定不在这里,所以可以递归在[mid1+1,end1]和[start2,end2]之间找;arra1[mid1]>arr2[mid2]的情况类似。
如果mid1+mid2>k,说明第K大的数比较小,根据上面的分析,下次递归时,可以舍弃掉[start1,mid1], (mid1,end1], [start2,mid2], (mid2,end2]中较大的那块。比如arr1[mid1]>arr2[mid2],则可以舍弃掉(mid2,end2]。
这样每次都可以舍弃掉两个数组中的某个的一半,时间复杂度是O(lgm+lgn),代码在GeeksforGeeks中。
更优的O(lg(k))的方法是,每次我们不是取中值,而是取arr1[k/2]和arr2[k/2],直接根据这两个值的大小关系去分割递归。代码见GeeksforGeeks中最后一个版本的代码,简洁。
针对这一题,求两个有序数组的中位数,如果两个有序数组的总长度len是奇数,则中位数就是两个有序数组中的第len/2大数;如果len是偶数,则中位数是第len/2和len/2的平均数,所以最多需要两次调用findKth就可以得到结果。完整代码如下:

class Solution {
private:
    int findKth(vector<int>& nums1, int s1, int e1, vector<int>& nums2, int s2, int e2, int k)
    {
        int len1 = e1 – s1 + 1, len2 = e2 – s2 + 1;
        if (len1 > len2)
            return findKth(nums2, s2, e2, nums1, s1, e1, k);
        if (len1 == 0)
            return nums2[s2 + k – 1];
        if (k == 1)
            return min(nums1[s1], nums2[s2]);
        int i = s1 + min(k / 2, len1) – 1, j = s2 + min(k / 2, len2) – 1;
        if (nums1[i] > nums2[j])
            return findKth(nums1, s1, e1, nums2, j + 1, e2, k – (j – s2 + 1));
        else
            return findKth(nums1, i + 1, e1, nums2, s2, e2, k – (i – s1 + 1));
    }
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        int m = nums1.size(), n = nums2.size();
        if ((m + n) % 2) {
            return findKth(nums1, 0, m – 1, nums2, 0, n – 1, (m + n) / 2 + 1);
        }
        else {
            return (findKth(nums1, 0, m – 1, nums2, 0, n – 1, (m + n) / 2) + findKth(nums1, 0, m – 1, nums2, 0, n – 1, (m + n) / 2 + 1)) / 2.0;
        }
    }
};

本代码提交AC,用时65MS。

三刷。

这题有点难,还是看官方题解吧: https://leetcode.com/problems/median-of-two-sorted-arrays/solution/

          left_part          |        right_part
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

如上图所示。其实本质是我们要对数组A和B进行划分,使得left_part_A加left_part_B的元素个数等于right_part_A加right_part_B的元素个数。因为总元素个数是m+n,所以总的left_part的个数应该是(m+n)/2,当然为了统一处理奇偶问题,可以让left_part数目多一点为(m+n+1)/2。那么很自然的,如果A的划分点为i的话,为了满足总的left_part数目为(m+n+1)/2,则B的划分点就要为(m+n+1)/2-i。

也就是说,如果A的划分点为i,B的划分点为(m+n+1)/2-i时,我们就能保证left_part和right_part的数目相等。我们可以想象一下,i和j相当于两个隔板,当i向右移动时,left_part_A元素增加,为了维持平衡,则j一定要向左移动。那么问题就转换为这个i到底等于多少才能找到中位数。

中位数的含义是,所有左边的数都小于它,所有右边的数都大于它。因为A[i-1]<A[i]和B[j-1]<B[j]是天然成立的,为了找中位数,还需要保证A[i-1]<B[j]和B[j-1]<A[i]。所有,我们找i的过程就是在找满足A[i-1]<B[j]和B[j-1]<A[i]的i的过程。

那么,很自然的解法就是,假设i是A的中点,即二分m/2,求出对应的j的位置:(m+n+1)/2-i。然后看看A[i-1]<B[j]和B[j-1]<A[i]是否都满足,如果是的话,就找到了i和j,也就找到了中位数,中位数就是在i和j隔板附近的4个数中间。如果不满足A[i-1]<B[j],即A[i-1]>B[j],说明i的隔板太靠右了,导致A[i-1]太大了,所以要把i往左移一点。类似的,如果不满足B[j-1]<A[i],则把i往右移一点。

如果还不理解的话,可以看油管上的视频讲解: https://youtu.be/LPFhl65R7ww,下面的代码就是模仿这个视频写的。

class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int m = nums1.size(), n = nums2.size();
		if (m > n)return findMedianSortedArrays(nums2, nums1);
		int low = 0, high = m;
		while (low <= high) {
			int partition1 = (low + high) / 2;
			int partition2 = (m + n + 1) / 2 - partition1;
			
			int maxleft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
			int minright1 = (partition1 == m) ? INT_MAX : nums1[partition1];

			int maxleft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
			int minright2 = (partition2 == n) ? INT_MAX : nums2[partition2];

			if (maxleft1 <= minright2 && maxleft2 <= minright1) {
				if ((m + n) % 2 == 0) {
					int mid1 = maxleft1 > maxleft2 ? maxleft1 : maxleft2;
					int mid2 = minright1 < minright2 ? minright1 : minright2;
					return (mid1 + mid2) / 2.0;
				}
				else {
					return maxleft1 > maxleft2 ? maxleft1 : maxleft2;
				}
			}
			else if (maxleft1 > minright2) {
				high = partition1 - 1;
			}
			else if (maxleft2 > minright1) {
				low = partition1 + 1;
			}
		}
		return 0;
	}
};

本代码提交AC,用时24MS。

hihoCoder 1139-二分·二分答案

hihoCoder 1139-二分·二分答案 #1139 : 二分·二分答案 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在上一回和上上回里我们知道Nettle在玩《艦これ》,Nettle在整理好舰队之后终于准备出海捞船和敌军交战了。 在这个游戏里面,海域是N个战略点(编号1..N)组成,如下图所示 其中红色的点表示有敌人驻扎,猫头像的的点表示该地图敌军主力舰队(boss)的驻扎点,虚线表示各个战略点之间的航线(无向边)。 在游戏中要从一个战略点到相邻战略点需要满足一定的条件,即需要舰队的索敌值大于等于这两点之间航线的索敌值需求。 由于提高索敌值需要将攻击机、轰炸机换成侦察机,舰队索敌值越高,也就意味着舰队的战力越低。 另外在每一个战略点会发生一次战斗,需要消耗1/K的燃料和子弹。必须在燃料和子弹未用完的情况下进入boss点才能与boss进行战斗,所以舰队最多只能走过K条航路。 现在Nettle想要以最高的战力来进攻boss点,所以他希望能够找出一条从起始点(编号为1的点)到boss点的航路,使得舰队需要达到的索敌值最低,并且有剩余的燃料和子弹。 特别说明:两个战略点之间可能不止一条航线,两个相邻战略点之间可能不止一条航线。保证至少存在一条路径能在燃料子弹用完前到达boss点。 提示:你在找什么? 输入 第1行:4个整数N,M,K,T。N表示战略点数量,M表示航线数量,K表示最多能经过的航路,T表示boss点编号, 1≤N,K≤10,000, N≤M≤100,000 第2..M+1行:3个整数u,v,w,表示战略点u,v之间存在航路,w表示该航路需求的索敌值,1≤w≤1,000,000。 输出 第1行:一个整数,表示舰队需要的最小索敌值。 样例输入 5 6 2 5 1 2 3 1 3 2 1 4 4 2 5 2 3 5 5 4 5 3 样例输出 3


本题的目标是在无向图中,求从点1到T的路径中的索敌值的最大值的最小值,且经过的路径不能超过k段。 在输入的时候,我们能得到所有索敌值的最大值high和最小值low,high值显然能够成功到达T点,且不超过k段,因为题目说了保证至少存在一条路径能在燃料子弹用完前到达boss点;low就不一定了。所以二分答案的意思就是在区间[low,high]中二分查找最小可行解。 假设函数f(x)能判断当索敌值为x时,是否能成功到达T点且不超过k段。则每二分一次就求一次f(mid),根据f(mid)的值调整区间[low,high]的端点。所以现在的关键就是函数f(x)。 f(x)可以使用广度优先搜索实现。实现的时候注意不能使用邻接矩阵保存图,有可能TLE或MLE,使用邻接表更好。完整代码如下: [cpp] #include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #include<queue> #include<vector> using namespace std; const int kMaxN = 10005, kINF = 0x3f, kMaxW = 1000005; vector<vector<int>> path; vector<vector<int>> powers; vector<bool> visit; int n, m, k, t; bool BFS(int power) { visit.clear(); visit.resize(n + 1, false); queue<int> Q; int u, v, len = 0;; Q.push(1); visit[1] = true; Q.push(-1); while (!Q.empty()&&len<k) { u = Q.front(); Q.pop(); if (u == -1) { if (Q.empty()) return false; else { len++; Q.push(-1); continue; } } for (int i = 0; i < path[u].size(); i++) { v = path[u][i]; if (!visit[v]&&powers[u][i] <= power) { if (v == t) return true; visit[v] = true; Q.push(v); } } } return false; } int main() { freopen("input.txt", "r", stdin); scanf("%d %d %d %d", &n, &m, &k, &t); path.resize(n + 1); powers.resize(n + 1); int u, v, w, low = kMaxW, high = 0; for (int i = 0; i < m; i++) { scanf("%d %d %d", &u, &v, &w); low = min(low, w); high = max(high, w); path[u].push_back(v); path[v].push_back(u); powers[u].push_back(w); powers[v].push_back(w); } while (low+1 < high) { int mid = (low + high) / 2; if (BFS(mid)) high = mid; else low = mid; } printf("%d\n", high); return 0; } [/cpp] 在BFS的时候可以单独保存每个点及该点此时的深度(len),也可以共用一个len,只需额外加入一个标记-1,当碰到-1时,说明已经遍历完一层了,深度加1。 本代码提交AC,用时189MS,内存8MB。]]>

hihoCoder 1133-二分·二分查找之k小数

hihoCoder 1133-二分·二分查找之k小数 #1133 : 二分·二分查找之k小数 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在上一回里我们知道Nettle在玩《艦これ》,Nettle的镇守府有很多船位,但船位再多也是有限的。Nettle通过捞船又出了一艘稀有的船,但是已有的N(1≤N≤1,000,000)个船位都已经有船了。所以Nettle不得不把其中一艘船拆掉来让位给新的船。Nettle思考了很久,决定随机选择一个k,然后拆掉稀有度第k小的船。 已知每一艘船都有自己的稀有度,Nettle现在把所有船的稀有度值告诉你,希望你能帮他找出目标船。 提示:非有序数组的二分查找之二 输入 第1行:2个整数N,k。N表示数组长度, 第2行:N个整数,表示a[1..N],保证不会出现重复的数,1≤a[i]≤2,000,000,000。 输出 第1行:一个整数t,表示t在数组中是第k小的数,若K不在数组中,输出-1。 样例输入 10 4 1732 4176 2602 6176 1303 6207 3125 1 1011 6600 样例输出 1732


给定一个无序序列,问序列中第k小的数是哪个。简单粗暴的方法是排序直接取a[k],复杂度为O(nlgn);还有一种O(lgn)的方法,采用了和hihoCoder 1128-二分·二分查找类似的方法,将序列不断二分成小于某个数和大于某个数的两部分,直到某一部分长度为k。 完整代码如下: [cpp] #include<iostream> #include<cstdio> #include<vector> using namespace std; int n, k; vector<int> a; int GetNumberK(int p, int q) { int m = a[p], i = p, j = q; while (i < j) { while (i < j&&a[j] > m) j–; a[i] = a[j]; while (i < j&&a[i] < m) i++; a[j] = a[i]; } if (k == i + 1)//(1) return m; else if (k < i + 1) return GetNumberK(p, i – 1); else { //k = k – (i – p + 1);//(2),因为(1)处判等的时候i取p,但分割之后p并没有从0开始,所以k还是k return GetNumberK(i + 1, q); } } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &k); a.resize(n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); if (k > n||k < 1) printf("-1\n"); else printf("%d\n", GetNumberK(0, n – 1)); return 0; } [/cpp] 本代码提交AC,用时69MS,内存3MB。 需要注意一点,代码中(2)不能出现,虽然递归在[i+1,q]内部查找第k – (i – p + 1)小的数,但是(1)处判等的时候,使用的i(即p)是相对[0,n-1]长度的,所以这里的k不需要剪短]]>