ChunNote
0%

leetCode-321:Create Maximum Number

发表于 分类于

问题描述

给定两个整数数组和一个数字 k，要求在两个数组中找出 k 个数字组成新的数组，数组元素的顺序跟原有数组的顺序保持不变。题目链接：**点我**

样例输入输出

输入：nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5

输出：[9, 8, 6, 5, 3]

输入：nums1 = [6, 7] nums2 = [6, 0, 4] k = 5

输出：[6, 7, 6, 0, 4]

问题解法

从第一个数组中挑出 m 个顺序跟原数组保持一致的最大数字的元素组成一个新的数组，从第二个数组中挑出 k - m 个顺序跟原数组保持一致的最大数字的元素组成一个新的数组，将这两个数组合并成一个数量为 k 的数组，保存在一个变量中，每次循环获得的数组都跟这个变量数组进行比较，并将大的数组更新到变量中。循环结束后，变量保持的数组就是求解的结果。代码如下

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
class Solution
{
    public int[] maxNumber(int[] nums1, int[] nums2, int k)
    {
        int[] result = new int[k];
        for (int i = 0; i <= k; i++)
        {
            int[] temp = merge(maxNumber(nums1, i), maxNumber(nums2, k - i));
            result = getMaxIntArray(result, temp);
        }

        return result;
    }

    private int[] getMaxIntArray(int[] nums1, int[] nums2)
    {
        if (nums1.length < nums2.length)
        {
            return nums2;
        }

        if (nums1.length > nums2.length)
        {
            return nums1;
        }

        for (int i = 0; i < nums1.length; i++)
        {
            if (nums1[i] < nums2[i])
            {
                return nums2;
            }

            if (nums1[i] > nums2[i])
            {
                return nums1;
            }
        }

        return nums2;
    }

    private int[] merge(List<Integer> nums1, List<Integer> nums2)
    {
        int[] result = new int[nums1.size() + nums2.size()];
        int i = 0;
        int j = 0;
        int index = 0;
        while (i < nums1.size() && j < nums2.size())
        {
            if (nums1.get(i) > nums2.get(j))
            {
                result[index] = nums1.get(i);
                index++;
                i++;
            }
            else if (nums1.get(i) < nums2.get(j))
            {
                result[index] = nums2.get(j);
                index++;
                j++;
            }
            else
            {
                int ii = i + 1;
                int jj = j + 1;
                boolean isFind = false;
                while (ii < nums1.size() && jj < nums2.size())
                {
                    if (nums1.get(ii) > nums2.get(jj))
                    {
                        result[index] = nums1.get(i);
                        index++;
                        i++;
                        isFind = true;
                        break;
                    }
                    else if (nums1.get(ii) < nums2.get(jj))
                    {
                        result[index] = nums2.get(j);
                        index++;
                        j++;
                        isFind = true;
                        break;
                    }
                    else
                    {
                        ii++;
                        jj++;
                    }
                }

                if (!isFind)
                {
                    if (ii == nums1.size())
                    {
                        result[index] = nums2.get(j);
                        index++;
                        j++;
                    }
                    else
                    {
                        result[index] = nums1.get(i);
                        index++;
                        i++;
                    }
                }
            }
        }

        while (i < nums1.size())
        {
            result[index] = nums1.get(i);
            index++;
            i++;
        }

        while (j < nums2.size())
        {
            result[index] = nums2.get(j);
            index++;
            j++;
        }

        return result;
    }

    private List<Integer> maxNumber(int[] nums, int k)
    {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++)
        {
            while (!stack.empty() && stack.peek() < nums[i] && stack.size() + nums.length - i > k)
            {
                stack.pop();
            }

            if (stack.size() < k)
            {
                stack.push(nums[i]);
            }
        }

        return stack;
    }
}

参考资料

http://leetcode.flowerplayer.com/2019/04/04/leetcode-321-create-maximum-number%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF%E5%88%86%E6%9E%90/