1.移除元素
给你一个数组 nums
和一个值 val
,你需要 原地 移除所有数值等于 val
的元素。元素的顺序可能发生改变。然后返回 nums
中与 val
不同的元素的数量。
假设 nums
中不等于 val
的元素数量为 k
,要通过此题,您需要执行以下操作:
(1)更改 nums
数组,使 nums
的前 k
个元素包含不等于 val
的元素。nums
的其余元素和 nums
的大小并不重要。
(2)返回 k
。
int removeElement(int* nums, int numsSize, int val)
{int count =1;while(count == 1){count = 0;for(int i=0;i<numsSize;i++){if(nums[i]==val){for(int j=i;j<numsSize-1;j++){nums[j] = nums[j+1];}numsSize--;count = 1;break;}}}return numsSize;
}
代码主要是通过遍历数组,如果没有雨val相同的值就就执行完全部程序,返回count的值。如果遍历过程中有val相同的值那么就删除(数组没有遍历完需要重新遍历),将count=1,重新遍历,直到遍历结果没有相同的值。
标准答案:双指针,遍历数组,将与val不相同的值按照顺序放到数组中。
int removeElement(int* nums, int numsSize, int val) {if (numsSize == 0) return 0;int k = 0; // 新数组的长度for (int i = 0; i < numsSize; i++) {if (nums[i] != val) {nums[k] = nums[i];k++;}}return k;
}
2.合并两个有序数组
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int j = 0;for(int i=0;i<n;i++){for(;j<m+i;j++){if(nums1[j]>nums2[i]){for(int k=m+i;k>j;k--){nums1[k] = nums1[k-1];}nums1[j] = nums2[i];break;}}if (j == m + i && m + i < nums1Size) {nums1[m + i] = nums2[i];} }}
代码是通过检测到nums1>nums2,那就将nums1的所有数据全部后移一位,然后将nums2的值插入到nums1中,但是这种编程方式,时间复杂度太大外层的for时间复杂度为o(n),内层就为o(m+i),两者时间复杂度就为o(n*m+n),主导为n*m。
标准答案:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int i = m - 1; // nums1 的有效元素索引int j = n - 1; // nums2 的有效元素索引int k = m + n - 1; // nums1 合并结果的索引while (i >= 0 && j >= 0) {if (nums1[i] > nums2[j]) {nums1[k] = nums1[i];i--;} else {nums1[k] = nums2[j];j--;}k--;}while (j >= 0) {nums1[k] = nums2[j];j--;k--;}
}