数据结构OJ题

轮转数组

在这里插入图片描述
思路1：
1.利用循环将最后一位数据放到临时变量（n）中
2.利用第二层循环将数据往后移一位
3.将变量（n）的数据放到数组第一位
时间复杂度：O(N^2)
空间复杂度：O(1)
思路2：
1.创建一个空间大小足够的数组
2.将数组按轮转的要求依次放入我们创建的数组里
3.再将新数组的内容依次存放的原数组中
时间复杂度：O(N)
空间复杂度：O(N)
这个思路就是利用空间来换时间了，随着计算机的发展，计算机的空间相比时间来说会廉价很多，必要情况下我们就可以选择使用空间来换取时间。
思路3：
1.将要轮转的元素首位调换
2.将不需要轮转的元素首位调换
3.将整个数组元素首位调换
时间复杂度：O(N)
空间复杂度：O(1)
具体流程如图所示：
在这里插入图片描述
很显然第三个思路是最好的，这里代码就只介绍思路3了。
代码实现：

void Swap(int* nums,int left,int right)
{while(left<right){int tmp=nums[left];nums[left]=nums[right];nums[right]=tmp;left++;right--;}
}
void rotate(int* nums, int numsSize, int k) {Swap(nums,0,numsSize-1-k);Swap(nums,numsSize-k,numsSize-1);Swap(nums,0,numsSize-1);
}

这个代码就完成了，但是在LeetCode提交出错了。
在这里插入图片描述
出错原因：只有一个数据但是他让我轮转两次。
解决办法：
在开始时让k模上一个数据个数。

void rotate(int* nums, int numsSize, int k) {k%=numsSize;Swap(nums,0,numsSize-1-k);Swap(nums,numsSize-k,numsSize-1);Swap(nums,0,numsSize-1);
}

题目链接： https://leetcode.cn/problems/rotate-array/submissions/567566749/

原地移除数组中所有元素val

要求：时间复杂度：O(N),空间复杂度：O(1)
在这里插入图片描述

案例：
在这里插入图片描述
思路：
1.定义两个变量left与right充当指针，都指向数组的第一个位置。
2.判断right当前的数据是否等于val
相等：right++
不相等：right指向的值赋值给left，right++，left++
3.返回left的数值就是当前数组有效数据的个数
left指向的时数组当前的位置，在它之前的数据都是有效的，因为下表是从0开始，所以数据个数就是最后一个数据的下表加一，推理得left值就是有效数据个数。
代码实现：

int removeElement(int* nums, int numsSize, int val) {int left=0;int right =0;while(right<numsSize){if(nums[right]==val){right++;}else{nums[left++]=nums[right++];}}return left;
}

题目链接：https://leetcode.cn/problems/remove-element/description/

删除有序数组中的重复项

在这里插入图片描述
案例：

思路：
1.定义两个变量left与right，一个指向下表0的位置，一个指向下表1的位置
2.判断left与right所指元素是否相等
相等：right++；
不相等：left++，right的值赋值给left，right++
3.返回left的值
代码实现：

int removeDuplicates(int* nums, int numsSize) {int left=0;int right =1;while(right<numsSize){if(nums[left]!=nums[right]){left++;nums[left]=nums[right];}right++;}return left+1;}

题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

合并两个有序数组

在这里插入图片描述
案例：

思路：
注意这里得题目要求，它的第一个数组的大小是第一个数组数据个数与第二个数组的数据个数之和，也就是它的大小可以刚好容纳两个数组的全部数据。
1.创建三个变量r，r1，r2
r指向第一个数组最后一个位置
r1指向数组1最后一个有效数据
r2指向数组2最后一个有效数据
2.比较两个数组最后一个有效数据大小
r1>r2:r1指向的数据放入r的空间，r1–；
r2>r1:r2指向的数据放入r的空间，r2–；
相等的话上面两个随便选一个方案即可
3.判断r2是否小于0
r2小于0，说明数组2的数据已经全部转移完，这个时候排序就完成了
r2>0,让数组2的剩余的没有比较的数据再依次放入数组1
代码实现：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int r1 = (m - 1);int r2 = (n - 1);int r = m + n - 1;while ((r1 >= 0) &&( r2 >= 0)){if (nums1[r1] >= nums2[r2]){nums1[r] = nums1[r1];r1--;}else{nums1[r] = nums2[r2];r2--;}r--;}while (r2 >= 0){nums1[r--]=nums2[r2--];}
}