-
lintcode 552 · 创建最大数 【算法 数组 贪心 hard】
题目
https://www.lintcode.com/problem/552/description
描述 给出两个长度分别是m和n的数组来表示两个大整数，数组的每个元素都是数字0-9。从这两个数组当中选出k个数字来创建一个最大数，其中k满足k <= m + n。选出来的数字在创建的最大数里面的位置必须和在原数组内的相对位置一致。返回k个数的数组。你应该尽可能的去优化算法的时间复杂度和空间复杂度。 样例 样例 1: 输入：nums1 = [3, 4, 6, 5]， nums2 = [9, 1, 2, 5, 8, 3]，k = 5 输出：[9, 8, 6, 5, 3] 解释： 从第一个数组选择[6, 5]，从第二个数组选择[9, 8, 3] 样例 2: 输入：nums1 = [6, 7]， nums2 = [6, 0, 4]，k = 5 输出：[6, 7, 6, 0, 4] 解释： 从第一个数组选择[6, 7]，从第二个数组选择[6, 0, 4] 样例 3: 输入：nums1 = [3, 9]， nums2 = [8, 9]，k = 3 输出：[9, 8, 9] 解释： 从第一个数组选择[9]，从第二个数组选择[8, 9]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
//思路： 左边选i个，右边选k - i个，merge出最大的 /* 参考：C++答案地址： https://blog.csdn.net/qq_31552435/article/details/52216546 比较双端队列【具有队列，栈的特性】 大小的逻辑 https://blog.csdn.net/Olivia_CFS/article/details/121596084 和C++答案这篇博客不同的是，java判断两个LinkedList的大小，需要自己写 而C++ 的vector本身就是可比较的- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
答案
public class Solution { /** * @param nums1: an integer array of length m with digits 0-9 * @param nums2: an integer array of length n with digits 0-9 * @param k: an integer and k <= m + n * @return: an integer array */ public int[] maxNumber(int[] nums1, int[] nums2, int k) { //思路： 左边选i个，右边选k - i个，merge出最大的 /* 参考：C++答案地址： https://blog.csdn.net/qq_31552435/article/details/52216546 比较双端队列【具有队列，栈的特性】 大小的逻辑 https://blog.csdn.net/Olivia_CFS/article/details/121596084 和C++答案这篇博客不同的是，java判断两个LinkedList的大小，需要自己写 而C++ 的vector本身就是可比较的 */ int len1 = nums1.length, len2 = nums2.length; int start = Math.max(k - len2, 0); int end = Math.min(k, len1); LinkedList<Integer> path = null; for (int k1 = start; k1 <= end; k1++) { LinkedList<Integer> path1 = f(nums1, k1); LinkedList<Integer> path2 = f(nums2, k - k1); // System.out.println("path1:" + path1); //System.out.println("path2:" + path2); LinkedList<Integer> cmp = connect(path1, path2); // System.out.println("cmp: " + cmp); //System.out.println("path:" + path); if (path != null) { for (int i = 0; i < cmp.size(); i++) { if (path.get(i) != cmp.get(i)) { if (cmp.get(i) > path.get(i)) { path = cmp; } break; } } } else { path = cmp; } } if(path.size()>0 && path.get(path.size()-1) ==null){ path.removeLast(); } int[] ans = new int[path.size()]; for (int i = 0; i < path.size(); i++) { ans[i] = path.get(i); } return ans; } /* · 输入数据 [1,6,5,4,7,3,9,5,3,7,8,4,1,1,4] [4,3,1,3,5,9] 21 输出数据 [4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,1,4,1,3,5,9] 期望答案 [4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,3,5,9,1,1,4] */ public static LinkedList<Integer> connect(LinkedList<Integer> ll1, LinkedList<Integer> ll2) { //https://blog.csdn.net/Olivia_CFS/article/details/121596084,比较逻辑参考C++代码 LinkedList<Integer> ll = new LinkedList<>(); while (ll1.size() + ll2.size() > 0) { //参考：https://blog.csdn.net/Olivia_CFS/article/details/121596084 //检查ll1,ll2谁更大 while (ll1.isEmpty() && !ll2.isEmpty()) ll.add(ll2.pollFirst()); while (!ll1.isEmpty() && ll2.isEmpty()) ll.add(ll1.pollFirst()); int max =1; int i1 =0,i2 =0; boolean findMax = false; int n1 = ll1.size(),n2 =ll2.size(); while (i1<n1 && i2 <n2){ if(ll2.get(i2) >ll1.get(i1)){ max =2; findMax =true; break; }else if(ll2.get(i2) < ll1.get(i1)){ max =1; findMax =true; break; }else{ i1++; i2++; } } //对于有的测试用例；这里很关键 if(findMax){ //如果找到最大的了，比如 ll1= 1 2 3 4 和 ll2=1 2 4 ，ll2更大 if(max ==1) ll.add(ll1.pollFirst()); if(max ==2) ll.add(ll2.pollFirst()); }else{//没有找到更大的，比如 ll1= 1 2 3 ll2= 1 2 3 4 那么ll2 更大 if(n1>n2) ll.add(ll1.pollFirst()); else ll.add(ll2.pollFirst()); } } return ll; } public static LinkedList<Integer> f(int[] nums, int k) { int drop = nums.length - k; LinkedList<Integer> ll = new LinkedList<>(); for (int num : nums) { while (drop > 0 && ll.size() > 0 && ll.peekLast() < num) { ll.removeLast(); drop--; } ll.add(num); } while (ll.size() > k) { ll.removeLast(); } return ll; } }- 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
本地测试代码
public class LC552 { public static int[] maxNumber(int[] nums1, int[] nums2, int k) { //思路： 左边选i个，右边选k - i个，merge出最大的 /* 参考：C++答案地址： https://blog.csdn.net/qq_31552435/article/details/52216546 比较双端队列【具有队列，栈的特性】 大小的逻辑 https://blog.csdn.net/Olivia_CFS/article/details/121596084 和C++答案这篇博客不同的是，java判断两个LinkedList的大小，需要自己写 而C++ 的vector本身就是可比较的 */ int len1 = nums1.length, len2 = nums2.length; int start = Math.max(k - len2, 0); int end = Math.min(k, len1); LinkedList<Integer> path = null; for (int k1 = start; k1 <= end; k1++) { LinkedList<Integer> path1 = f(nums1, k1); LinkedList<Integer> path2 = f(nums2, k - k1); // System.out.println("path1:" + path1); //System.out.println("path2:" + path2); LinkedList<Integer> cmp = connect(path1, path2); // System.out.println("cmp: " + cmp); //System.out.println("path:" + path); if (path != null) { for (int i = 0; i < cmp.size(); i++) { if (path.get(i) != cmp.get(i)) { if (cmp.get(i) > path.get(i)) { path = cmp; } break; } } } else { path = cmp; } } if(path.size()>0 && path.get(path.size()-1) ==null){ path.removeLast(); } int[] ans = new int[path.size()]; for (int i = 0; i < path.size(); i++) { ans[i] = path.get(i); } return ans; } /* · 输入数据 [1,6,5,4,7,3,9,5,3,7,8,4,1,1,4] [4,3,1,3,5,9] 21 输出数据 [4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,1,4,1,3,5,9] 期望答案 [4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,3,5,9,1,1,4] */ public static LinkedList<Integer> connect(LinkedList<Integer> ll1, LinkedList<Integer> ll2) { //https://blog.csdn.net/Olivia_CFS/article/details/121596084,比较逻辑参考C++代码 LinkedList<Integer> ll = new LinkedList<>(); while (ll1.size() + ll2.size() > 0) { //参考：https://blog.csdn.net/Olivia_CFS/article/details/121596084 //检查ll1,ll2谁更大 while (ll1.isEmpty() && !ll2.isEmpty()) ll.add(ll2.pollFirst()); while (!ll1.isEmpty() && ll2.isEmpty()) ll.add(ll1.pollFirst()); int max =1; int i1 =0,i2 =0; boolean findMax = false; int n1 = ll1.size(),n2 =ll2.size(); while (i1<n1 && i2 <n2){ if(ll2.get(i2) >ll1.get(i1)){ max =2; findMax =true; break; }else if(ll2.get(i2) < ll1.get(i1)){ max =1; findMax =true; break; }else{ i1++; i2++; } } //对于有的测试用例；这里很关键 if(findMax){ //如果找到最大的了，比如 ll1= 1 2 3 4 和 ll2=1 2 4 ，ll2更大 if(max ==1) ll.add(ll1.pollFirst()); if(max ==2) ll.add(ll2.pollFirst()); }else{//没有找到更大的，比如 ll1= 1 2 3 ll2= 1 2 3 4 那么ll2 更大 if(n1>n2) ll.add(ll1.pollFirst()); else ll.add(ll2.pollFirst()); } } return ll; } public static LinkedList<Integer> f(int[] nums, int k) { int drop = nums.length - k; LinkedList<Integer> ll = new LinkedList<>(); for (int num : nums) { while (drop > 0 && ll.size() > 0 && ll.peekLast() < num) { ll.removeLast(); drop--; } ll.add(num); } while (ll.size() > k) { ll.removeLast(); } return ll; } public static void main(String[] args) { test99(); //test99ok(); // test1(); //test2(); // test3(); //test4(); } public static void test99() { int[] nums1 =arr99, nums2 = arr100; int k1 = k99; int[] data1 = maxNumber(nums1, nums2, k1); for (int i : data1) { System.out.print(i + ","); } System.out.println(); int[] nums11 =arr99, nums21 = arr100; int k11 = k99; int[] data11 = new Solution().maxNumber(nums11, nums21, k11); for (int i : data11) { System.out.print(i + ","); } int n = data1.length; int incr = 0; for (int i = 0; i < n; i++) { if (data1[i] != data11[i]) { System.out.println(i + " 正确：" + data11[i]+" 当前："+ data1[i]); if (incr++ == 3) break; } } } public static void test99ok() { int[] nums1 =arr99, nums2 = arr100; int k1 = k99; int[] data1 = new Solution().maxNumber(nums1, nums2, k1); for (int i : data1) { System.out.print(i + ","); } System.out.println(); } public static void test1() { int[] nums1 = {3, 4, 6, 5}, nums2 = {9, 1, 2, 5, 8, 3}; int k1 = 5; int[] data1 = maxNumber(nums1, nums2, k1); for (int i : data1) { System.out.print(i + " "); } System.out.println(); } public static void test2() { int[] nums1 = {6, 7}, nums2 = {6, 0, 4}; int k1 = 5; int[] data1 = maxNumber(nums1, nums2, k1); for (int i : data1) { System.out.print(i + " "); } System.out.println(); } public static void test3() { int[] nums1 = {3, 9}, nums2 = {8, 9}; int k1 = 3; int[] data1 = maxNumber(nums1, nums2, k1); for (int i : data1) { System.out.print(i + " "); } System.out.println(); } public static void test4() { int[] nums1 = {1, 6, 5, 4, 7, 3, 9, 5, 3, 7, 8, 4, 1, 1, 4}, nums2 = {4, 3, 1, 3, 5, 9}; int k1 = 21; int[] data1 = maxNumber(nums1, nums2, k1); for (int i : data1) { System.out.print(i + " "); } System.out.println(); } static int[] arr99 = {2,0,2,1,2,2,2,2,0,1,0,0,2,0,2,0,2,1,0,1,1,0,1,0,1,2,1,1,1,0,1,2,2,1,0,0,1,2,1,2,2,1,1,0,1,2,0,2,0,1,2,0,2,1,1,1,2,0,0,1,0,2,1,2,0,1,0,0,0,1,2,1,0,1,1,2,0,2,2,0,0,1,1,2,2,1,1,2,2,1,0,1,2,0,1,2,2,0,0,0,2,0,2,0,2,2,0,1,1,1,1,2,2,2,2,0,0,2,2,2,2,0,2,0,1,0,0,2,1,0,0,2,0,2,1,1,1,1,0,1,2,0,2,1,0,1,1,1,0,0,2,2,2,0,2,1,1,1,2,2,0,0,2,2,2,2,2,0,2,0,2,0,2,0,0,1,0,1,1,0,0,2,1,1,2,2,2,1,2,2,0,0,2,1,0,2,1,2,1,1,1,0,2,0,1,1,2,1,1,0,0,1,0,1,2,2,2,0,2,2,1,0,1,2,1,2,0,2,2,0,1,2,2,1,2,2,1,1,2,2,2,2,2,1,2,0,1,1,1,2,2,2,0,2,0,2,0,2,1,1,0,2,2,2,1,0,2,1,2,2,2,0,1,1,1,1,1,1,0,0,0,2,2,0,1,2,1,0,0,2,2,2,2,1,0,2,0,1,2,0}, arr100={1,1,1,0,0,1,1,0,2,1,0,1,2,1,0,2,2,1,0,2,0,1,1,0,0,2,2,0,1,0,2,0,2,2,2,2,1,1,1,1,0,0,0,0,2,1,0,2,1,1,2,1,2,2,0,2,1,0,2,0,0,2,0,2,2,1,0,1,0,0,2,1,1,1,2,2,0,0,0,1,1,2,0,2,2,0,1,0,2,1,0,2,1,1,1,0,1,1,2,0,2,0,1,1,2,0,2,0,1,2,1,0,2,0,1,0,0,0,1,2,1,2,0,1,2,2,1,1,0,1,2,1,0,0,1,0,2,2,1,2,2,0,0,0,2,0,0,0,1,0,2,0,2,1,0,0,1,2,0,1,1,0,1,0,2,2,2,1,1,0,1,1,2,1,0,2,2,2,1,2,2,2,2,0,1,1,0,1,2,1,2,2,0,0,0,0,0,1,1,1,2,1,2,1,1,0,1,2,0,1,2,1,2,2,2,2,0,0,0,0,2,0,1,2,0,1,1,1,1,0,1,2,2,1,0,1,2,2,1,2,2,2,0,2,0,1,1,2,0,0,2,2,0,1,0,2,1,0,0,1,1,1,1,0,0,2,2,2,2,0,0,1,2,1,1,2,0,1,2,1,0,2,0,0,2,1,1,0,2,1,1,2,2,0,1,0,2,0,1,0}; static int k99= 600; static class Solution { /** * @param nums1 an integer array of length m with digits 0-9 * @param nums2 an integer array of length n with digits 0-9 * @param k an integer and k <= m + n * @return an integer array */ public int[] maxNumber(int[] nums1, int[] nums2, int k) { // Write your code here if (k == 0) return new int[0]; int m = nums1.length, n = nums2.length; if (m + n < k) return null; if (m + n == k) { int[] results = merge(nums1, nums2, k); return results; } else { int max = m >= k ? k : m; int min = n >= k ? 0 : k - n; int[] results = new int[k]; for (int i = 0; i < k; ++i) results[i] = -0x7ffffff; for (int i = min; i <= max; ++i) { int[] temp = merge(getMax(nums1, i), getMax(nums2, k - i), k); results = isGreater(results, 0, temp, 0) ? results : temp; } return results; } } private int[] merge(int[] nums1, int[] nums2, int k) { int[] results = new int[k]; if (k == 0) return results; int i = 0, j = 0; for (int l = 0; l < k; ++l) { results[l] = isGreater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++]; } return results; } private boolean isGreater(int[] nums1, int i, int[] nums2, int j) { for (; i < nums1.length && j < nums2.length; ++i, ++j) { if (nums1[i] > nums2[j]) return true; if (nums1[i] < nums2[j]) return false; } return i != nums1.length; } private int[] getMax(int[] nums, int k) { if (k == 0) return new int[0]; int[] results = new int[k]; int i = 0; for (int j = 0; j < nums.length; ++j) { while (nums.length - j + i > k && i > 0 && results[i - 1] < nums[j]) i--; if (i < k) results[i++] = nums[j]; } return results; } } } /* 366 ms 时间消耗 · 21.32 MB 空间消耗 · 输入数据 [1,6,5,4,7,3,9,5,3,7,8,4,1,1,4] [4,3,1,3,5,9] 21 输出数据 [4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,1,4,1,3,5,9] 期望答案 [4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,3,5,9,1,1,4] */- 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
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
-
相关阅读:
来自五年架构师的职业感悟，学历+路线+风口，助你成就美好未来
MySQL(变量 存储过程 触发器 函数)
论文解读（MVGRL）Contrastive Multi-View Representation Learning on Graphs
Docker学习笔记
LuatOS 开发指南
尝试使用java写redis分布式锁
08【MyBatis之动态SQL】
用动态ip登录账号的风险高不高？
基于javaweb的在线服装销售商城系统(java+springboot+vue+mysql)
c# cad二次开发实现注记搜索跟扩展属性搜索，并点击即可定位到位置，添加了界面操作
- 原文地址：https://blog.csdn.net/weixin_37991016/article/details/132914740
