LeetCode刷题系列之《双指针解数组》网站首页 技术教程

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

阿博历练记 2023-05-22 09:01:49

简介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);
}