题目描述
给你一个正整数数组 nums
,请你返回一个数组 answer
,你需要将 nums
中每个整数进行数位分割后,按照 nums
中出现的 相同顺序 放入答案数组中。
对一个整数进行数位分割,指的是将整数各个数位按原本出现的顺序排列成数组。
- 比方说,整数
10921
,分割它的各个数位得到[1,0,9,2,1]
。
样例
输入:nums = [13,25,83,77]
输出:[1,3,2,5,8,3,7,7]
解释:
- 分割 13 得到 [1,3]。
- 分割 25 得到 [2,5]。
- 分割 83 得到 [8,3]。
- 分割 77 得到 [7,7]。
answer = [1,3,2,5,8,3,7,7]。answer 中的数字分割结果按照原数字在数组中的相同顺序排列。
输入:nums = [7,1,3,9]
输出:[7,1,3,9]
解释:nums 中每个整数的分割是它自己。
answer = [7,1,3,9]。
限制
1 <= nums.length <= 1000
1 <= nums[i] <= 10^5
算法
(模拟) $O(n \log m)$
- 按照题意模拟,为了处理方便,可以倒序,并从低位开始处理每个数字,最后再将答案反转就是正确的顺序。
时间复杂度
- 每个数字 $m$ 需要 $O(\log m)$ 的时间,故总时间复杂度为 $O(n \log m)$。
空间复杂度
- 需要 $O(n \log m)$ 的额外空间存储答案。
C++ 代码
class Solution {
public:
vector<int> separateDigits(vector<int>& nums) {
vector<int> ans;
for (int i = nums.size() - 1; i >= 0; i--) {
int x = nums[i];
while (x) {
ans.push_back(x % 10);
x /= 10;
}
}
reverse(ans.begin(), ans.end());
return ans;
}
};