登录2553. 分割数组中数字的数位
解法
思路和算法
这道题要求将给定的正整数数组 $\textit{nums}$ 中的所有正整数按数位分割，保持数位顺序存入答案数组。需要首先遍历数组 $\textit{nums}$ 得到数位总数，然后将每个正整数按数位分割并存入答案数组。
首先遍历数组 $\textit{nums}$ 得到所有正整数的数位总数 $\textit{totalLength}$，然后创建长度为 $\textit{totalLength}$ 的答案数组 $\textit{answer}$，再次遍历数组 $\textit{nums}$，遍历过程中维护答案数组的当前下标 $\textit{index}$，对于每个正整数，执行如下操作。
-
用 $\textit{start}$ 表示当前正整数的数位填入答案数组的起始下标，$\textit{start} = \textit{index}$。
-
每次将 $\textit{num}$ 的最低位填入 $\textit{answer}[\textit{index}]$，然后将 $\textit{index}$ 的值增加 $1$，重复该操作直到 $\textit{num}$ 的所有位都填入答案数组。
-
当前正整数 $\textit{num}$ 填入答案数组的下标范围是 $[\textit{start}, \textit{index} - 1]$，为按照数位从低到高的顺序填入。为了和数组 $\textit{nums}$ 中的数位顺序保持一致，需要将答案数组的下标范围 $[\textit{start}, \textit{index} - 1]$ 的子数组翻转。
遍历结束之后，即可得到答案数组。
代码
###Java
class Solution {
public int[] separateDigits(int[] nums) {
int totalLength = 0;
for (int num : nums) {
totalLength += getLength(num);
}
int[] answer = new int[totalLength];
int index = 0;
for (int num : nums) {
int start = index;
int temp = num;
while (temp != 0) {
answer[index] = temp % 10;
index++;
temp /= 10;
}
reverse(answer, start, index - 1);
}
return answer;
}
public int getLength(int num) {
int length = 0;
while (num != 0) {
length++;
num /= 10;
}
return length;
}
public void reverse(int[] answer, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = answer[i];
answer[i] = answer[j];
answer[j] = temp;
}
}
}
###C#
public class Solution {
public int[] SeparateDigits(int[] nums) {
int totalLength = 0;
foreach (int num in nums) {
totalLength += GetLength(num);
}
int[] answer = new int[totalLength];
int index = 0;
foreach (int num in nums) {
int start = index;
int temp = num;
while (temp != 0) {
answer[index] = temp % 10;
index++;
temp /= 10;
}
Reverse(answer, start, index - 1);
}
return answer;
}
public int GetLength(int num) {
int length = 0;
while (num != 0) {
length++;
num /= 10;
}
return length;
}
public void Reverse(int[] answer, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = answer[i];
answer[i] = answer[j];
answer[j] = temp;
}
}
}
###C++
class Solution {
public:
vector<int> separateDigits(vector<int>& nums) {
int totalLength = 0;
for (int num : nums) {
totalLength += getLength(num);
}
vector<int> answer(totalLength);
int index = 0;
for (int num : nums) {
int start = index;
int temp = num;
while (temp != 0) {
answer[index] = temp % 10;
index++;
temp /= 10;
}
reverse(answer, start, index - 1);
}
return answer;
}
int getLength(int num) {
int length = 0;
while (num != 0) {
length++;
num /= 10;
}
return length;
}
void reverse(vector<int>& answer, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
swap(answer[i], answer[j]);
}
}
};
###Python
class Solution:
def separateDigits(self, nums: List[int]) -> List[int]:
answer = []
index = 0
for num in nums:
start = index
temp = num
while temp != 0:
answer.append(temp % 10)
index += 1
temp //= 10
self.reverse(answer, start, index - 1)
return answer
def getLength(self, num: int) -> int:
length = 0
while num != 0:
length += 1
num //= 10
return length
def reverse(self, answer: List[int], start: int, end: int) -> None:
i, j = start, end
while i < j:
answer[i], answer[j] = answer[j], answer[i]
i += 1
j -= 1
###C
int getLength(int num) {
int length = 0;
while (num != 0) {
length++;
num /= 10;
}
return length;
}
void reverse(int* answer, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = answer[i];
answer[i] = answer[j];
answer[j] = temp;
}
}
int* separateDigits(int* nums, int numsSize, int* returnSize) {
int totalLength = 0;
for (int i = 0; i < numsSize; i++) {
totalLength += getLength(nums[i]);
}
int* answer = (int*) malloc(sizeof(int) * totalLength);
*returnSize = totalLength;
int index = 0;
for (int i = 0; i < numsSize; i++) {
int start = index;
int temp = nums[i];
while (temp != 0) {
answer[index] = temp % 10;
index++;
temp /= 10;
}
reverse(answer, start, index - 1);
}
return answer;
}
###Go
func separateDigits(nums []int) []int {
totalLength := 0
for _, num := range nums {
totalLength += getLength(num)
}
answer := make([]int, totalLength)
index := 0
for _, num := range nums {
start := index
temp := num
for temp != 0 {
answer[index] = temp % 10
index++
temp /= 10
}
reverse(answer, start, index - 1)
}
return answer
}
func getLength(num int) int {
length := 0
for num != 0 {
length++
num /= 10
}
return length
}
func reverse(answer []int, start int, end int) {
for i, j := start, end; i < j; i, j = i + 1, j - 1 {
answer[i], answer[j] = answer[j], answer[i]
}
}
###JavaScript
var separateDigits = function(nums) {
let totalLength = 0;
for (let num of nums) {
totalLength += getLength(num);
}
let answer = new Array(totalLength);
let index = 0;
for (let num of nums) {
let start = index;
let temp = num;
while (temp !== 0) {
answer[index] = temp % 10;
index++;
temp = Math.floor(temp / 10);
}
reverse(answer, start, index - 1);
}
return answer;
};
var getLength = function(num) {
let length = 0;
while (num !== 0) {
length++;
num = Math.floor(num / 10);
}
return length;
};
var reverse = function(answer, start, end) {
for (let i = start, j = end; i < j; i++, j--) {
let temp = answer[i];
answer[i] = answer[j];
answer[j] = temp;
}
};
###TypeScript
function separateDigits(nums: number[]): number[] {
let totalLength = 0;
for (let num of nums) {
totalLength += getLength(num);
}
let answer = new Array(totalLength);
let index = 0;
for (let num of nums) {
let start = index;
let temp = num;
while (temp !== 0) {
answer[index] = temp % 10;
index++;
temp = Math.floor(temp / 10);
}
reverse(answer, start, index - 1);
}
return answer;
};
function getLength(num: number): number {
let length = 0;
while (num !== 0) {
length++;
num = Math.floor(num / 10);
}
return length;
};
function reverse(answer: number[], start: number, end: number): void {
for (let i = start, j = end; i < j; i++, j--) {
let temp = answer[i];
answer[i] = answer[j];
answer[j] = temp;
}
};
复杂度分析
-
时间复杂度：$O(n \log_{10} m)$，其中 $n$ 是数组 $\textit{nums}$ 的长度，$m$ 是数组 $\textit{nums}$ 的最大元素。计算答案数组的长度与将数位填入答案数组的时间是 $O(n \log_{10} m)$。
-
空间复杂度：$O(1)$。注意返回值不计入空间复杂度。
