Leetcode 321


  Posted on 13 Apr 2017
greedy


Tutorial


The dynamic programming solution is rather straight forward. The greedy solution is like this. We enumerate how many digits we pick from each array. Each time we get the optimal respectively from two arrays, then merge them together. It is not possible that the overall optimal solution is from sub-optimal solutions for the two arrays. So this solution is valid. Then, the problem is how to select a optimal subarray of a certain length from the array and how to merge two arrays. Please see the code for details.

Solution


class Solution {
	int n, m;
	public:
	vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
		vector<int> ret = vector<int> (k);
		fill(ret.begin(), ret.end(), 0);
		n = nums1.size();
		m = nums2.size();
		for (int i = 0; i <= k; i++) {
			if (n < i || m < k - i) {
				continue;
			}
			vector<int> a = select(nums1, i);
			vector<int> b = select(nums2, k - i);
			vector<int> c = merge(a, b);
			if (lexicographical_compare(ret.begin(), ret.end(), c.begin(), c.end()))
				ret = c;
		}
		return ret;
	}

	vector<int> merge(vector<int> &a, vector<int> &b) {
		auto qa = deque<int> (a.begin(), a.end());
		auto qb = deque<int> (b.begin(), b.end());
		auto ret = vector<int> ();
		while (!(qa.empty() && qb.empty())) {
			if (lexicographical_compare(qa.begin(), qa.end(), qb.begin(), qb.end())) {
				ret.push_back(qb.front());
				qb.pop_front();
			} else {
				ret.push_back(qa.front());
				qa.pop_front();
			}
		}
		return ret;
	}

	vector<int> select(vector<int> &nums, int k) {
		vector<int> ret = vector<int> ();
		for (int i = 0; i < nums.size(); i++) {
			while (ret.size() > 0 && ret[ret.size() - 1] < nums[i] && k - ret.size() <= nums.size() - 1 - i)
				ret.pop_back();
			if (ret.size() < k)
				ret.push_back(nums[i]);
		}
		return ret;
	}
};