目录
一:顺序表-移除元素
二:顺序表-删除有序数组中的重复项
三:顺序表-合并两个有序数组
四:顺序表-旋转数组
五:顺序表-数组形式的整数加法
一:顺序表-移除元素
题型链接:27. 移除元素 - 力扣(LeetCode)
题目要求:原地移除数组中所有的元素val,要求时间复杂度为O(N),空间复杂度为O(1)
以 【 nums = [0,1,2,2,3,0,4,2], val = 2 】为例:
解答步骤:
int removeElement(int* nums, int numsSize, int val) {int i=0,j=0;for(i=0,j=0;j<numsSize;){if(nums[j]==val){j++;} else{nums[i++] = nums[j++];}}return i;
}
二:顺序表-删除有序数组中的重复项
题型链接:26. 删除有序数组中的重复项 - 力扣(LeetCode)
题目要求:删除排序数组中的重复项
以【 nums = [0,0,1,1,1,2,2,3,3,4] 】为例:
解答步骤:
int removeDuplicates(int* nums, int numsSize) {int i=0,j=0;for(i=0,j=0;j<numsSize;){if(nums[i]==nums[j]){j++;}else{nums[++i] = nums[j++];}}return i+1;
}
三:顺序表-合并两个有序数组
题型链接:88. 合并两个有序数组 - 力扣(LeetCode)
题目要求:合并两个有序数组
解题思路:从后往前大小比较法
以【 nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 】为例:
解答步骤:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int end1 = m-1;int end2 = n-1;int end = m+n-1;while(end1>=0 && end2>=0){if(nums1[end1]<nums2[end2]){nums1[end--] = nums2[end2--];}else{nums1[end--] = nums1[end1--];}}while(end2>=0){nums1[end--] = nums2[end2--];}
}
四:顺序表-旋转数组
题型链接:189. 轮转数组 - 力扣(LeetCode)
题目要求:将数组旋转
解题思路:三段逆置法
向右轮转k个位置:
- 先将整个数组进行逆置。
- 再将【0,k-1】范围内的数组逆置
- 最后【k,numsSize-1】范围内的数组逆置
解答步骤:
//逆序
void Reverse(int* a,int left,int right)
{while(left<right){int tmp = a[left];a[left]= a[right];a[right] = tmp;++left;--right;}}void rotate(int* nums, int numsSize, int k) {k %= numsSize;Reverse(nums,0,numsSize-1);Reverse(nums,0,k-1);Reverse(nums,k,numsSize-1);
}
五:顺序表-数组形式的整数加法
题型链接:989. 数组形式的整数加法 - 力扣(LeetCode)
题目要求:数组形式的整数加法
解题思路:
- 先得到的所求的逆序数组
- 再将其逆置转换过来
解答步骤:
int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {int* tmp = (int*)malloc(sizeof(int) * fmax(10, numSize + 1));*returnSize = 0;for(int i = numSize-1; i>=0; i--){int sum = num[i] + k % 10;k /= 10;if(sum>=10){k++;sum -= 10;}tmp[(*returnSize)++] = sum;}for(; k>0; k/=10){tmp[(*returnSize)++] = k%10;}for(int i=0; i<(*returnSize)/2; i++){int ret = tmp[i];tmp[i] = tmp[(*returnSize)-1-i];tmp[(*returnSize)-1-i] = ret;}return tmp;
}