当前位置: 代码迷 >> 综合 >> JAVA算法:创建最大数(JAVA代码)
  详细解决方案

JAVA算法:创建最大数(JAVA代码)

热度:2   发布时间:2024-01-15 19:19:28.0

JAVA算法:创建最大数(JAVA代码)

给定长度分别为 m 和 n 的两个数组,其元素由 0-9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 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]
示例 2:

输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]
示例 3:

输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]


算法思路

首先采用分治法的思路,我们知道这K个数字中,必然有i个数组来自nums1,而剩下的k-i个数字必然来自nums2。那么问题变成从nums1中获取i个数,这i个数构成的数字最大,且这i个数字的相对位置不变。再从nums2中获取k-i个数,这k-i个数构成的数字最大,且这k-i个数字的相对位置不变。

那么我们如何将这两个结果合并起来获得我们最终的结果呢?这里很像归并算法的merge过程,我们从两个数组的开头获取最大的值加进来呗。那如果出现相同的值怎么办?那么继续比较,直到遇到第一个不相同的数字,然后选择数字较大的那个数组。

算法设计

package com.bean.algorithm.basic;public class CreateMaxNumber {public int[] maxNumber(int[] nums1, int[] nums2, int k) {// 结果集int[] result = new int[k];// nums1最多能够提供的数字的个数int