细语呢喃

技术改变生活

0%

leetcode Create Maximum Number

发表于 分类于 ， 阅读次数： 评论数：

leetcode Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9] nums2 = [8, 9] k = 3 return [9, 8, 9]

题目地址：leetcode Create Maximum Number

题意：

给定两个长度为m和n的数组，他们由0~9的数组组成，现在，让你通过这两个数组中的数字组建一个长度为k 的数组（k<=m+n) ,原来数组的相对顺序要保留。

思路：

递归写法TLE了。

问了一下CJL的思路~其实都差不多。我是直接原串找当前符合条件的最大的值，然后递归，他是枚举长度，然后找符合长度的。。。

第7个AC哈哈

我A这题的时候。。。这题一共 7个AC，410+次提交。。。通过率1%...  难度medium，现在改成hard了。。。

枚举第一个数组A的个数i，那么数组B的个数就确定了 k -i。

然后枚举出A和B长度分别为i和k-i的最大子数组，（可以用栈，类似leetcode Remove Duplicate Letters）

最后组合看看哪个大。

组合的过程类似合并排序，看看哪个数组大，就选哪个。

枚举数组长度复杂度O(k)，找出最大子数组O(n)，合并的话O(k^2)

而k最坏是m+n,所以总的复杂度就是O((m+n)^3)

Idea:

To find the maximum ,we can enumerate how digits we should get from nums1 , we suppose it is i.

So ,  the digits from nums2 is K - i.

And we can use a stack to get the get maximum number(x digits) from one array.（just like leetcode Remove Duplicate Letters）

OK, Once we choose two maximum subarray , we should combine it to the answer.

It is just like merger sort, but we should pay attention to the case: the two digital are equal.

we should find the digits behind it to judge which digital we should choose now.

In other words,we should judge which subarry is bigger than the other.

That's all.

The algorithm is O((m+n)^3) in the worst case.

If you have any question or suggest, I am happy you can comment on my blog .

Thanks, merry christmas :)

Solution

Java 21ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Created by hrwhisper on 2015/11/23.
 * https://www.hrwhisper.me/leetcode-create-maximum-number/
 */

public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] ans = new int[k];
        for (int i = Math.max(k - nums2.length, 0); i <= Math.min(nums1.length, k); i++) {
            int[] res1 = get_max_sub_array(nums1, i);
            int[] res2 = get_max_sub_array(nums2, k - i);
            int[] res = new int[k];
            int pos1 = 0, pos2 = 0, tpos = 0;

            while (pos1 < res1.length  pos2 < res2.length) {
                res[tpos++] = greater(res1, pos1, res2, pos2) ? res1[pos1++] : res2[pos2++];
            }

            if (!greater(ans, 0, res, 0))
                ans = res;
        }

        return ans;
    }

    public boolean greater(int[] nums1, int start1, int[] nums2, int start2) {
        for (; start1 < nums1.length && start2 < nums2.length; start1++, start2++) {
            if (nums1[start1] > nums2[start2]) return true;
            if (nums1[start1] < nums2[start2]) return false;
        }
        return start1 != nums1.length;
    }

    public int[] get_max_sub_array(int[] nums, int k) {
        int[] res = new int[k];
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            while (len > 0 && len + nums.length - i > k && res[len - 1] < nums[i]) {
                len--;
            }
            if (len < k)
                res[len++] = nums[i];
        }
        return res;
    }
}

 

C++ 60ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
	vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
		vector<int> ans(k, 0);
		for (int i = max(0, k - (int)nums2.size()); i <= min(k, (int)nums1.size()); i++) {
			vector<int> res1 = get_max_sub_array(nums1, i);
			vector<int> res2 = get_max_sub_array(nums2, k - i);
			vector<int> res(k, 0);
			int pos1 = 0, pos2 = 0, tpos = 0;
			while (pos1 < res1.size() || pos2 < res2.size()) {
				res[tpos++] = greater(res1, pos1, res2, pos2) ? res1[pos1++] : res2[pos2++];
			}
			if (!greater(ans, 0, res, 0))
				ans = res;
		}
		return ans;
	}

	bool greater(const vector<int> & a, int start1, const vector<int> &b, int start2) {
		for (; start1 < a.size() && start2 < b.size(); start1++, start2++) {
			if (a[start1] > b[start2]) return true;
			if (a[start1] < b[start2]) return false;
		}
		return start1 != a.size();
	}

	vector<int> get_max_sub_array(const vector<int> &nums, const int& k) {
		vector<int> res(k,0);
		int len = 0 , n = nums.size();
		for (int i = 0; i < n; i++) {
			while (len && len + n - i > k && nums[i] > res[len - 1])
				len--;
			if (len < k)
				res[len++] = nums[i];
		}
		return res;
	}
};

 

Python 636ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[int]
        """

        def get_max_sub_array(nums, k):
            res , n = [] ,len(nums)
            for i in xrange(n):
                while res and len(res) + n - i > k and nums[i] > res[-1]:
                    res.pop()
                if len(res) < k:
                    res.append(nums[i])
            return res

        ans = [0] * k
        for i in xrange(max(0, k - len(nums2)), min(k, len(nums1)) + 1):
            res1 = get_max_sub_array(nums1, i)
            res2 = get_max_sub_array(nums2, k - i)
            ans = max(ans, [max(res1, res2).pop(0) for _ in xrange(k)])
        return ans

 

只需要greater函数的解释

为什么只需要比较两个子序列大小呢？

来看看我写的比较早的版本，主要注意合并的时候。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * Created by hrwhisper on 2015/11/23.
 * https://www.hrwhisper.me/leetcode-create-maximum-number/
 */

public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int get_from_nums1 = Math.min(nums1.length, k);
        int[] ans = new int[k];
        for (int i = Math.max(k - nums2.length, 0); i <= get_from_nums1; i++) {
            int[] res1 = new int[i];
            if (i > 0)
                res1 = solve(nums1, i);
            int[] res2 = new int[k - i];
            if (k - i > 0)
                res2 = solve(nums2, k - i);
            int pos1 = 0, pos2 = 0, tpos = 0;
            int[] res = new int[k];
            while (res1.length > 0 && res2.length > 0 && pos1 < res1.length && pos2 < res2.length) {
                if (res1[pos1] > res2[pos2])
                    res[tpos++] = res1[pos1++];
                else if (res1[pos1] < res2[pos2])
                    res[tpos++] = res2[pos2++];
                else {
                    int x = pos1;
                    int y = pos2;
                    while (x < res1.length && y < res2.length && res1[x] == res2[y]) {
                        x++;
                        y++;
                    }
                    if (x < res1.length && y < res2.length) {
                        if (res1[x] < res2[y]) {
                            res[tpos++] = res2[pos2++];
                        } else {
                            res[tpos++] = res1[pos1++];
                        }
                    } else if (x < res1.length) {
                        res[tpos++] = res1[pos1++];
                    } else {
                        res[tpos++] = res2[pos2++];
                    }
                }
            }
            while (pos1 < res1.length)
                res[tpos++] = res1[pos1++];
            while (pos2 < res2.length)
                res[tpos++] = res2[pos2++];

            if (updateAns(ans, res))
                ans = res;
        }
        return ans;
    }

    public boolean updateAns(int[] ans, int[] res) {
        for (int i = 0; i < ans.length; i++) {
            if (ans[i] > res[i])
                return false;
            if (ans[i] < res[i])
                return true;
        }
        return false;
    }

    public int[] solve(int[] nums, int k) {
        int[] res = new int[k];
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            while (len > 0 && len + nums.length - i > k && res[len - 1] < nums[i]) {
                len--;
            }
            if (len < k)
                res[len++] = nums[i];
        }
        return res;
    }
}

最大子数组 res1 用x来遍历，res2用y来遍历。

对于相等的情况，往后找直到其中一个比另一个大，或者一个到了数组的长度

  • 对于都未到达数组长度的，哪个大选哪个

  • 若x1 <  res1.length  ，说明x2到达数组的长度了，选res1 ，因为要给后面的数更早出现的机会

    • [3,3,4]  [3,3] k = 5
    • 答案为[3,3,4,3,3]
    • 选择的过程中，因为第二个到末尾了，第一个还没到，显然4比较大，要给4早出现的机会。所以选res1

  • 否则选res2（可能是x2 <  res2.length 也可能是 x1 == res1.length && x2 == res2.length）

根据上面的，只要比较res1比res2未选的部分哪个大就选哪个即可。

所以，简写为：

1
2
3
while (pos1 < res1.length  pos2 < res2.length) {
                res[tpos++] = greater(res1, pos1, res2, pos2) ? res1[pos1++] : res2[pos2++];
}

至于greater函数，可以和updateAns函数合并成如下：

1
2
3
4
5
6
7
public boolean greater(int[] nums1, int start1, int[] nums2, int start2) {
       for (; start1 < nums1.length && start2 < nums2.length; start1++, start2++) {
           if (nums1[start1] > nums2[start2]) return true;
           if (nums1[start1] < nums2[start2]) return false;
       }
       return start1 != nums1.length;
   }

 

递归寻找最大子数组

java 150ms,递归寻找效率肯定不如用栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int get_from_nums1 = Math.min(nums1.length, k);
        int[] ans = new int[k];
        for (int i = Math.max(k - nums2.length, 0); i <= get_from_nums1; i++) {
            int[] res1 = new int[i];
            if (i > 0)
                res1 = solve(nums1, 0, res1, 0, i);
            int[] res2 = new int[k - i];
            if (k - i > 0)
                res2 = solve(nums2, 0, res2, 0, k - i);
            int pos1 = 0, pos2 = 0, tpos = 0;
            int[] res = new int[k];
            while (res1.length > 0 && res2.length > 0 && pos1 < res1.length && pos2 < res2.length) {
                if (res1[pos1] > res2[pos2])
                    res[tpos++] = res1[pos1++];
                else if (res1[pos1] < res2[pos2])
                    res[tpos++] = res2[pos2++];
                else {
                    int x = pos1;
                    int y = pos2;
                    while (x < res1.length && y < res2.length && res1[x] == res2[y]) {
                        x++;
                        y++;
                    }
                    if (x < res1.length && y < res2.length) {
                        if (res1[x] < res2[y]) {
                            res[tpos++] = res2[pos2++];
                        } else {
                            res[tpos++] = res1[pos1++];
                        }
                    } else if (x < res1.length) {
                        res[tpos++] = res1[pos1++];
                    } else {
                        res[tpos++] = res2[pos2++];
                    }
                }
            }
            while (pos1 < res1.length)
                res[tpos++] = res1[pos1++];
            while (pos2 < res2.length)
                res[tpos++] = res2[pos2++];

            if (updateAns(ans, res))
                ans = res;
        }
        return ans;
    }

    public boolean updateAns(int[] ans, int[] res) {
        for (int i = 0; i < ans.length; i++) {
            if (ans[i] > res[i])
                return false;
            if(ans[i] < res[i])
                return true;
        }
        return true;
    }

    public int[] solve(int[] nums1, int start, int[] res, int cur, int k) {
        if (cur == k) return res;
        int[] dig_num1 = new int[10];
        for (int i = 0; i < 10; i++)
            dig_num1[i] = -1;

        for (int i = start; i < nums1.length; i++) {
            if (dig_num1[nums1[i]] == -1) {
                dig_num1[nums1[i]] = i;
            }
        }

        int pos1 = -1;
        for (int i = 0; i < 10; i++) {
            if (dig_num1[i] >= 0)
                pos1 = i;
        }

        if (pos1 >= 0 && nums1.length - dig_num1[pos1] + cur < k) {
            pos1--;
            while (pos1 > 0 && (dig_num1[pos1] == -1  nums1.length - dig_num1[pos1] + cur < k))
                pos1--;
        }
        if (pos1 < 0) return res;
        res[cur] = pos1;
        return solve(nums1, dig_num1[pos1] + 1, res, cur + 1, k);
    }
}
请我喝杯咖啡吧~