LeetCode刷题系列之《双指针解数组》

各位csdn的友友们好啊，今天阿博给大家分享几道leetcode上的经典数组题，通过这次的学习，相信友友们可以更全面的认识指针和数组🍉🍉🍉

一.题目描述

二.逻辑分析

三.代码解析

一.题目描述

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
示例1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素.
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

逻辑分析

代码解析

fast为0

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

fast为1

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

二.题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素.
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

逻辑分析

代码解析

int removeElement(int* nums, int numsSize, int val){int left=0;int right=0;for(right=0;right<numsSize;right++){if(nums[right]!=val){nums[left]=nums[right];     //双指针的应用left++;}}return  left;
}

int removeElement(int* nums, int numsSize, int val){int left=0;int right=0;while(right<numsSize){if(nums[right]!=val){nums[left++]=nums[right++];     //双指针的应用}else{right++;}}return  left;
}

这里友友们也可以这样写哦，都是正确的，友友们可以根据自己喜好去选择.🌺🌺🌺

三.题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列.
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

逻辑分析

这里阿博给友友们再熟悉一下memmove的功能，它适用于所有的类型

代码解析

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){if(n==0&&m==0){return;}for(int i=0;i<n;i++){nums1[m+i]=nums2[i];}//memmove(nums1+m,nums2,4*n);int i=0;for(i=0;i<n+m-1;i++){if(nums1[j]>nums1[j+1]){int temp=nums1[j];nums1[j]=nums1[j+1];nums1[j+1]=temp;}}
}

四.题目描述

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数.
输入：[3,0,1]
输出：2
输入：[9,6,4,2,3,5,7,0,1]
输出：8

逻辑分析

代码解析

int missingNumber(int* nums, int numsSize)
{int x=(1+numsSize)*numsSize/2;int i=0;for(i=0;i<numsSize;i++){x-=nums[i];}return  x;
}

五.题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数.
输入: nums = [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]

逻辑分析

代码解析

void rotate(int* nums, int numsSize, int k)
{k%=numsSize;while(k--){int temp=nums[numsSize-1];int i=0;for(i=numsSize-1;i>0;i--){nums[i]=nums[i-1];}nums[0]=temp;}
}

友友们注意了，这样写虽然正确，但是时间复杂度会非常高，就是ko(N)，我们考虑最坏的打算就是N^2,所以这里我们采用三段逆置

逻辑分析

代码解析

void reverse(int* nums, int begin, int end)
{while(begin < end){int tmp = nums[begin];nums[begin] = nums[end];nums[end] = tmp;++begin;--end;}
}// 三趟逆置倒的思路
void rotate(int* nums, int numsSize, int k){if(k > numsSize){k %= numsSize;}reverse(nums, 0, numsSize-1);reverse(nums, 0, k-1);reverse(nums, k, numsSize-1);
}

好了，友友们，以上就是阿博今天的分享了，希望友友们能够有所收获，后续阿博会继续给友友们带来更多干货知识，让我们下期再见.🌹🌹🌹