图库网站建设,搜索引擎排名优化方案,苏州网站制作排名优化,品牌型网站制作哪题目链接 Leetcode.321 拼接最大数 hard 题目描述
给定长度分别为 m m m 和 n n n 的两个数组#xff0c;其元素由 0 ∼ 9 0 \sim 9 0∼9 构成#xff0c;表示两个自然数各位上的数字。现在从这两个数组中选出 k k k ( k ≤ m n ) (k \leq m n) (k≤mn) 个数字拼接成…题目链接 Leetcode.321 拼接最大数 hard 题目描述
给定长度分别为 m m m 和 n n n 的两个数组其元素由 0 ∼ 9 0 \sim 9 0∼9 构成表示两个自然数各位上的数字。现在从这两个数组中选出 k k k ( k ≤ m n ) (k \leq m n) (k≤mn) 个数字拼接成一个新的数要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k k 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 k k 个元素组成的最大数其中有 x x x 个元素来自 n u m s 1 nums1 nums1那么就有 k − x k - x k−x 个元素来自 n u m s 2 nums2 nums2。
我们定义 m a x _ s e q u e n c e ( S , m ) max\_sequence(S,m) max_sequence(S,m) 表示从集合 S S S 中选出 m m m 个元素构成的最大数元素之间要保持在集合 S S S 中的相对位置。 s 1 m a x _ s e q u e n c e ( n u m s 1 , x ) s1 max\_sequence(nums1,x) s1max_sequence(nums1,x) s 1 s1 s1 表示从集合 n u m s 1 nums1 nums1 中选出 x x x 个元素组成的最大数 s 2 m a x _ s e q u e n c e ( n u m s 2 , k − x ) s2 max\_sequence(nums2,k-x) s2max_sequence(nums2,k−x) s 2 s2 s2 表示从集合 n u m s 2 nums2 nums2 中选出 k − x k-x k−x 个元素组成的最大数
我们最后再将 s 1 s1 s1 和 s 2 s2 s2 拼接成一个最大数 S S S那么这个 S S S 就是答案之一。所以我们就要遍历 x x x 求出所有的 S S S最后返回最大的那个。
在实现上 m a x _ s e q u e n c e ( S , m ) max\_sequence(S,m) max_sequence(S,m) 可以利用单调栈实现
如果 S . s i z e ( ) ≤ m S.size() \leq m S.size()≤m那么直接返回集合 S S S 即可我们定义一个栈 s t k stk stk因为我们要返回的是 m m m 个元素组成的最大数也就是说 s t k stk stk 最终有 m m m 个元素即 s t k stk stk 能够弹出去的元素最多只有 d e l S . s i z e ( ) − m del S.size() - m delS.size()−m 个。假设当前遍历到的元素为 x x x如果 x s t k . t o p ( ) x stk.top() xstk.top() 并且 d e l 0 del 0 del0那么就可以弹出栈顶元素因为我们要是 s t k stk stk 中的数字典序尽可能的大。最终返回 s t k stk stk 即可。需要注意的是如果 S S S 中所有元素都相同 或者 S S S 是一个非降序的序列那么 s t k stk stk 中就没有弹出的元素一共就有 S . s i z e ( ) S.size() S.size() 个元素我们只需要前 m m m 个即可。
在这里需要介绍一个 STL algorithm 库的函数 lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
templateclass InputIt1, class InputIt2
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,InputIt2 first2, InputIt2 last2)
{for (; (first1 ! last1) (first2 ! last2); first1, (void) first2){if (*first1 *first2)return true;if (*first2 *first1)return false;}return (first1 last1) (first2 ! last2);
}上述这个函数的作用是判断区间一 [ f i r s t 1 , l a s t 1 ) [first1,last1) [first1,last1) 字典序是否不大于 区间二 [ f i r s t 2 , l a s t 2 ) [first2,last2) [first2,last2)。
是的话最终返回 true否返回 false
时间复杂度 O ( m n k 2 ) O(m n k^2) O(mnk2)
C代码
class Solution {
public:vectorint max_sequence(vectorint vec,int k){int n vec.size();if(n k) return vec;vectorint stk;int del n - k;for(int i 0;i n;i){while(stk.size() vec[i] stk.back() del){del--;stk.pop_back();}stk.push_back(vec[i]);}stk.resize(k);return stk;}vectorint maxNumber(vectorint nums1, vectorint nums2, int k) {int m nums1.size() , n nums2.size();vectorint res(k,0);for(int x max(0,k - n);x min(k,m);x){vectorint temp;auto s1 max_sequence(nums1,x);auto s2 max_sequence(nums2,k - x);auto it1 s1.begin() , it2 s2.begin();while(it1 ! s1.end() || it2 ! s2.end()){temp.push_back(lexicographical_compare(it1,s1.end(),it2,s2.end() )? *it2 : *it1);}res lexicographical_compare(res.begin(),res.end(),temp.begin(),temp.end()) ? move(temp) : res;}return res;}
};
