您现在的位置是:首页 >技术教程 >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);
}

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

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。