顺序表的列题（力扣）和旋转数组

03-09 阅读 0评论

文章目录

一.删除有序数组中的重复项（取自力扣）
$顺序表的列题（力扣）和旋转数组,顺序表的列题（力扣）和旋转数组,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第1张$
（图片来源网络，侵删）
二.合并两个有序数组（取自力扣）

三.旋转数组（多解法）

前言

见面我们说到了顺序表今天来分享几个有关于顺序表的题目

一.删除有序数组中的重复项（取自力扣）

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

$顺序表的列题（力扣）和旋转数组,顺序表的列题（力扣）和旋转数组,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第2张$

（图片来源网络，侵删）

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

遇到这种题目的话，我们首先就是画图，代码题目，首先都是画图，在图上来写代码，因为画图，他可以直观的来表述一些做法光用脑子想是一个不可取的选择，删除重复的数字，我们之前其实是有过做类似于找单身狗的题目，我们用的是异或的方法，但是他现在是在一个有序的数组里，也就是顺序表中，那么我们该如何去解决这个问题呢？

这个题目就有一点，我们之前去完善顺序表的思想，在指定位置，删除某个数字的时候，我们运用了那个双指针的想法，其实做这个题目也是一样的，也是需要用指针多个指针来做。我们首先来创造3个指针，dst，i，j我们就是要删除重复的数

那我该如何去实现了，这里我们思路是这样的，dst它用来保留数字，就是说有重复的数字删去其他的啊，他就作为保留的那个数字，然后i与j他们两个如果相等的话，就让这去加加往前移动，一旦他们两个不相等了，再把i赋给dst，然后再让i去等于j以此类推

$顺序表的列题（力扣）和旋转数组,顺序表的列题（力扣）和旋转数组,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第6张$

（图片来源网络，侵删）

翻译下来就是这样的

1.nums[i]==nums[j];
    j++;
2.nums[i]!=nums[j]；
    dst++；
    i=j；
     j++;

然后就可以写题了，注意:当j走到最后一个数的时候，他会越界，所以说还会剩下一个数，因此我们在while循环走完之后，我们还要单独把最后一个数再放进数组才算正确

int removeDuplicates(int* nums, int numsSize) 
{
	if (numsSize == 0)
		return 0;
	int i = 0;
	int j = 1;
	int dst = 0;
	while (j  
二.合并两个有序数组（取自力扣） 
 
 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 
 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。 
 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。 
 示例 1： 
 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。 
 
这个题目我个人做的时候感觉还是非常难的，没有做出来，当然自己的水平也本来不是很高，我们做题的时候都要放低自己的心态，学习是没有尽头的 
 
 
 这个地方我们要先理解一个的归并的思想，就是说给我两个数，我该如何让他们按顺序排下来呢？谁的小，谁加加让后把小的那个放下来 
 
 
 
 但是这个题目，用这种从前往后的比小的不成立，所以马上转变思路，从后往前比大 
 
这波我们选择创建三个指针，因为根据题目来看的话，我要全部放在第一个数组里，所以我设三个指针两个指针都是M和N去决定的另外一个指针放在第一个数组的最后一个，然后两两比较，如果大了的话就往后放，然后减减跟上面的思想是一样的，只不过是一个往前一个往后。 
 
 
 注意：这个地方有个特殊情况，就是说我们上面讨论的是nums2先结束，如果nums1先结束的话，则num2的剩余要移到num1上去 
 
 
然后就可以作答了 
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
	int end1 = m - 1, end2 = n - 1;
	int end = m + n - 1;
	while (end1 >= 0 && end2 >= 0)
	{
		if (nums1[end1] > nums2[end2])
		{
			nums1[end] = nums1[end1];
				end--;
			    end1--;
		}
		else
		{
			nums1[end] = nums2[end2];
			    end--;
			    end2--;
		}
	}
	while (end2 >= 0)//特殊情况
	{
		nums1[end] = nums2[end2];
			end--;
		    end2--;
	}
} 
三.旋转数组（多解法） 
 
 示例：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例：
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4] 
 
3.1暴力求解，遍历法（时间O(N*K)，空间O(1)) 
这个方法就是一般能想到的方法，用两个for循环去暴力的求解，第一个或循环很简单，第二个或循环有一个细节，我们可以设置一个变量为他就代表下一个位置要放的值。 
void rotate(int* nums, int numsSize, int k)
{
	for (int i = 0; i