数据结构与算法面试题:实现一个函数 splice(int[] a, int b[], int n, int m) 将数组 b 插入到数组 a 的第 n 个位置上去,并将其后面的元素后移 m 个位置,同时更新数组 a 的长度
简介:实现一个函数 splice(int[] a, int b[], int n, int m) 将数组 b 插入到数组 a 的第 n 个位置上去,并将其后面的元素后移 m 个位置,同时更新数组 a 的长度
算法思路
算法思路:
- 本题要求我们在一个已有数组a中插入另一个数组b,并将a的长度相应更新。其实现方式比较直观:先复制后面的一段元素,再用从后往前的顺序把前面的元素向右移动m步,然后把b插入到n的位置上即可。
- 注意,在实现过程中需要确保程序不会出现越界情况。
下面是C++实现的代码,每一行都添加了详细注释:
#include <iostream> #include <cstring> using namespace std; void splice(int a[], int b[], int n, int m) { // splice函数的实现 int len_a = sizeof(a) / sizeof(a[0]); // 数组长度为 a_len int len_b = sizeof(b) / sizeof(b[0]); // 数组长度为 b_len memcpy(a + n + m, a + n, (len_a - n) * sizeof(int)); // 先复制原数组中待移动的部分 for (int i = n + m - 1; i >= n; i--) { // 再从后往前移动前面的部分 a[i] = a[i - m]; } for (int i = n, j = 0; j < m; i++, j++) { // 将 b 数组替换到 a 数组的 n 位置处 a[i] = b[j]; } cout << "The new array a: "; for (int i = 0; i < len_a + m; i++) { // 输出更新后的数组 cout << a[i] << " "; } cout << endl; } int main() { int a[] = {1, 2, 3, 4, 5}; // 数组a int b[] = {6, 7, 8, 9, 10}; // 数组b int n = 2, m = 5; // 在第n个位置插入数组b并移动m格 splice(a, b, n, m); // 调用splice函数 return 0; }
需要注意的是,上述代码中实现了两个基础操作:首先使用memcpy函数复制了原数组中待移动的一段元素;随后在for循环中从后往前移动前面的元素。最后通过又一个循环将数组b插入到a的第n个位置上。
同时,在C++中sizeof运算符返回的是类型或变量存储所占用的字节数,因此对于数组来说,需要除以单个元素的大小(此处为sizeof(int))才能求出其元素个数。
- Java版本
class Solution { public void splice(int[] a, int[] b, int n, int m) { // splice方法的实现 int len_a = a.length; // 数组长度为 len_a int len_b = b.length; // 数组长度为 len_b System.arraycopy(a, n, a, n + m, len_a - n); // 先复制原数组中待移动的部分 for (int i = n + m - 1; i >= n; i--) { // 再从后往前移动前面的部分 a[i] = a[i - m]; } for (int i = n, j = 0; j < m; i++, j++) { // 将 b 数组复制到 a 数组的 n 位置处 a[i] = b[j]; } System.out.print("The new array a: "); for (int i = 0; i < len_a + m; i++) { // 输出更新后的数组 System.out.print(a[i] + " "); } System.out.println(); } public static void main(String[] args) { Solution sol = new Solution(); int[] a = {1, 2, 3, 4, 5}; // 数组a int[] b = {6, 7, 8, 9, 10}; // 数组b int n = 2, m = 5; // 在第n个位置插入数组b并移动m格 sol.splice(a, b, n, m); // 调用splice方法 } }
在Java中,System.arraycopy方法拷贝从指定源数组的一个位置开始,到指定目标数组的一个位置结束,并取代原数组中相应位置上的元素。需要注意的是,其具体实现中需要保证程序不会出现越界情况,同时打印出更新后的数组结果也有一定区别。