文章目录
-
一.删除有序数组中的重复项（取自力扣）
-
二.合并两个有序数组（取自力扣）
-
三.旋转数组（多解法）
前言
见面我们说到了顺序表今天来分享几个有关于顺序表的题目
一.删除有序数组中的重复项（取自力扣）
给你两个按 非递减顺序 排列的整数数组
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 中的元素。
遇到这种题目的话，我们首先就是画图，代码题目，首先都是画图，在图上来写代码，因为画图，他可以直观的来表述一些做法光用脑子想是一个不可取的选择，删除重复的数字，我们之前其实是有过做类似于找单身狗的题目，我们用的是异或的方法，但是他现在是在一个有序的数组里，也就是顺序表中，那么我们该如何去解决这个问题呢？
这个题目就有一点，我们之前去完善顺序表的思想，在指定位置，删除某个数字的时候，我们运用了那个双指针的想法，其实做这个题目也是一样的，也是需要用指针多个指针来做。我们首先来创造3个指针，dst，i，j我们就是要删除重复的数
那我该如何去实现了，这里我们思路是这样的，dst它用来保留数字，就是说有重复的数字删去其他的啊，他就作为保留的那个数字，然后i与j他们两个如果相等的话，就让这去加加往前移动，一旦他们两个不相等了，再把i赋给dst，然后再让i去等于j以此类推
翻译下来就是这样的
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 < numsSize)
{
if (nums[i] == nums[j])
{
j++;
}
else
{
nums[dst] = nums[i];
dst++;
i = j;
j++;
}
}
//注意就在这里体现
nums[dst] = nums[i];
dst++;
return dst;
}二.合并两个有序数组（取自力扣）
给你两个按 非递减顺序 排列的整数数组
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<k; i++)//大循环，旋转最后一个数
{
int replace = nums[numsSize - 1];
for (int j = 0; j<numsSize; j++)//小循环，把最后一个数放在第一个，然后都往后面挪
{
int temp = nums[j];
nums[j] = replace;
replace = temp;
}
}
}
3.2开辟数组法，以空间换时间（时间O(N)，空间O(N))
这种解法也是我做出题时所使用的解法，这个解法唯一的坏处就是空间换时间，有些题目他不一定允许你空间复杂度为大N，我个人感觉这个方法比较无脑，比之前的暴力求解还要容易想。他就是开辟了一个新的数组，把k位置前的元素拿出来和位置后的元素拿出来，再放到新的数组里就可以了。
void rotate(int* nums, int numsSize, int k)
{
k =k% numsSize;//k可能会存在大于数组元素个数的情况
int *tmp = (int *)malloc(sizeof(int)*numsSize);
int initial = 0;
//原后半
for (int i=numsSize-k; i < numsSize; i++)
{
arr[initial] = nums[i];//先将后面的拷入tmp中
initial++;
}
//原前半
for (int j = 0; j< numsSize - k; j++)
{
arr[initial] = nums[j];//再将前面的拷入tmp中
initial++;
}
for (int l = 0; l < numsSize; l++)
{
nums[l] = tmp[l];//拷贝回原数组
}
}
3.3逆置大法（时间O(N)，空间O(1))最优解
这个方法太强了，但是思维量太大，很难想出来。
//先写出一个逆置函数
void reverse(int *nums, int left, int right)
{
while (left<right)
{
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k)
{
if(k>numsSize);
{
k %= numsSize;//K=numsSize
}
//前n-k逆置,注意是下标
reverse(nums, 0, numsSize -k- 1);
//后个k逆置
reverse(nums, numsSize -k, numsSize - 1);
//整体逆置
rverse(nums, 0, numsSize - 1);
}
总结
顺序表到此就告一段落了，其实顺序表还是有很多缺陷的，所以我们才会开启后面的学习人生也是这样子的，只有不断地完善自己才能取得成功。
