👉移动零👈
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
进阶：你能尽量减少完成的操作次数吗？
思路一
利用下标 src 找到不为0的元素，再借助中间变量 tmp 将下标为 dst 的元素和 下标为 src 的元素进行交换。遍历数组之后，所有0就被移动到数组的末尾。具体移动操作：当 nums[src] == 0 时，src++；而当 nums[src] != 0 时，进行交换操作后，src++ dst++。
void moveZeroes(int* nums, int numsSize) { int dst=0; int src=0; while(src<numsSize) { if(nums[src]!=0) { int tmp=nums[src]; nums[src]=nums[dst]; nums[dst]=tmp; src++; dst++; } else src++; } }
思路二
利用下标 src 找不是零的元素，将不是零的元素放在下标 dst 的位置上，然后再将数组末尾的元素全部赋值为零。
void moveZeroes(int* nums, int numsSize) { int src = 0; int dst = 0; while (src < numsSize) { if (nums[src] != 0) { nums[dst++] = nums[src++]; } else { src++; } } //将数组末尾的元素赋值为0 while (dst < numsSize) { nums[dst++] = 0; } }
👉调整奇数偶数顺序👈
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：
nums = [1,2,3,4]输出：
[1,3,2,4]注：
[3,1,2,4]也是正确的答案之一。
提示：
- 0 <= nums.length <= 50000
- 0 <= nums[i] <= 10000
思路：跟移动零的思路一样，只是判断条件变了。
int* exchange(int* nums, int numsSize, int* returnSize) { int index=0; int pos=0; while(index<numsSize) { if(nums[index]%2) { int tmp=nums[index]; nums[index]=nums[pos]; nums[pos]=tmp; index++; pos++; } else index++; } *returnSize=numsSize; return nums; }
👉颜色分类👈
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
提示：
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
进阶：
你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？
思路：这道题如果使用 qsort 库函数来解的话，将会显得很简单。在这里，博主就不介绍这种方法了。在这里给大家介绍另一种方法，见下图：
void sortColors(int* nums, int numsSize) { int left = 0; int right = numsSize - 1; int src = 0; while (src <= right) { if (nums[src] < 1) { int tmp = nums[src]; nums[src] = nums[left]; nums[left] = tmp; left++; src++; } else if (nums[src] == 1) src++; else { int tmp = nums[src]; nums[src] = nums[right]; nums[right] = tmp; right--; } } }
分析：这道题其实推而广之，num的值可以为任意整数。只不过这道题的num值为1。最需要注意的就是，循环条件是src <= left。如果循环条件错了的话，就无法通过测试了。还需要注意的是，nums[src] 和 num 的大小关系不同，对应着不同的情况。
👉有序数组的平方👈
给你一个按非递减顺序 排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序 排序。
示例 1：
输入：
nums = [-4,-1,0,3,10]输出：
[0,1,9,16,100]解释：
平方后，数组变为 [16,1,0,9,100]；排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104 nums 已按 非递减顺序 排序
进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题
思路一
先将数组中的元素先平方，然后再利用快排对数组进行排序。时间复杂度为O(N+N*logN)，空间复杂度为O(1)。
int cmp(int* a, int* b) { return *a - *b; } int* sortedSquares(int* nums, int numsSize, int* returnSize) { int* num = (int*)malloc(sizeof(int) * numsSize); for (int i = 0; i < numsSize; i++) { nums[i] = nums[i] * nums[i]; } qsort(nums, numsSize, sizeof(int), cmp); *returnSize = numsSize; return nums; }
思路二
数组其实是有序的， 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。见下图分析：
int* sortedSquares(int* nums, int numsSize, int* returnSize) { int* num = (int*)malloc(sizeof(int) * numsSize); if(num == NULL) { *returnSize = 0; return num; } int left = 0; int right = numsSize - 1; int index = numsSize - 1; while (left <= right) { if ((nums[left] * nums[left]) > (nums[right] * nums[right])) { num[index--] = nums[left] * nums[left]; left++; } else { num[index--] = nums[right] * nums[right]; right--; } } *returnSize = numsSize; return num; }
👉有效的山脉数组👈
给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：
arr.length >= 3
在 0 < i < arr.length - 1 条件下，存在 i 使得：
arr[0] < arr[1]< ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
示例 1：
输入：
arr = [2,1]输出：
false
示例 2：
输入：
arr = [3,5,5]输出：
false
示例 3：
输入：
arr = [0,3,2,1]输出：
true
提示：
- 1 <= arr.length <= 10^4
- 0 <= arr[i] <= 10^4
思路：判断是山峰，主要就是要严格地保证从左边到中间和从右边到中间是递增的。这样可以使用两个指针，left 和 right，让其按照如下规则移动，如图：
注意：因为left和right是数组下标，移动的过程中注意不要数组越界。如果left或者right没有移动，说明是一个单调递增或者递减的数组，依然不是山峰。
、
bool validMountainArray(int* arr, int arrSize) { if (arrSize < 3) return false; int left = 0; int right = arrSize - 1; //防止越界 while ((left < arrSize - 1) && (arr[left] < arr[left + 1])) { left++; } //防止越界 while ((right > 0) && (arr[right] < arr[right - 1])) { right--; } //如果left或者right在起始位置，说明不是山峰 if ((left == right) && (left != 0) && (right != arrSize - 1)) return true; return false; }
👉总结👈
本篇博客主要讲了五道题目，这五道题目或多或少都运用到了双指针的思想。双指针这个思想非常地重要，希望大家能够学会！如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家啦！！！💖💝❣️
