原地去重问题和合并有序数组问题

简介: 原地去重问题和合并有序数组问题

原地去重问题

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。这是leetcode上的一道题


这里我们用两个指针来计算去重后的元素个数

dst是用来记录去重后有多少值以及给他们赋值

src则是来检查重复的值,将值赋给dst

代码表示如下

int removeDuplicates(int* nums, int numsSize)
{
  int src = 1;
  int dst = 0;
  while (src < numsSize)
  {
    if (nums[dst] == nums[src])
    {
      src++;
    }
    else
    {
      nums[++dst] = nums[src++];
    }
  }
  return dst + 1;
}

这是接口型写法

至于这里为什么要加一呢? 因为实际上des表示的是数组的下标 下标比实际的元素少一

所以要加一

合并有序数组问题

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。


请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。


注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。也是

leetcode上的一个题


这一题也是一个典型的三指针问题 我们可以设立三个指针 一个指向数组m的最末尾位置

一个指向数组n的末尾位置 一个指向数组m的元素个位置

我们可以比较指向m或者n的两个指针的大小

如果说m的大就放在最后面去 m–

反之n就放在最后面去 n–

当数组n指向0位置前面的时候 可以不用变化了

当数组m指向0位置前面之后 还需要将n前面的所有数组迁移到数组m上去

代码表示如下


void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
  int end1 = m - 1;
  int end2 = n - 1;
  int dst = m + n - 1;
  while (end1 >= 0 && end2 >= 0)
  {
    if (nums1[end1] > nums2[end2])
    {
      nums1[dst--] = nums1[end1--];
    }
    else
    {
      nums1[dst--] = nums2[end2--];
    }
  }
  while (end2 >= 0)
  {
    nums1[dst--] = nums2[end2--];
  }
}


还是接口型写法

以上便是本文所有内容了,如有错误请各位大佬不吝赐教,感谢留言

目录
相关文章
|
算法 前端开发
前端算法-删除有序数组中的重复项
前端算法-删除有序数组中的重复项
|
3月前
|
Python
【面试题解答】一个有序数组 nums ,原地删除重复出现的元素
【面试题解答】一个有序数组 nums ,原地删除重复出现的元素
32 0
|
6月前
|
算法 Java
算法题 合并两个有序数组
算法题 合并两个有序数组
30 1
|
6月前
|
存储 C++
合并两个有序数组(C++)
合并两个有序数组(C++)
74 0
|
6月前
|
算法
滑动窗口算法&删除排序数组中重复项
滑动窗口算法&删除排序数组中重复项
|
6月前
|
算法 程序员 测试技术
【算法训练-数组 四】【数组合并】:合并两个有序数组
【算法训练-数组 四】【数组合并】:合并两个有序数组
52 0
27. 移除元素 26. 删除有序数组中的重复项 88. 合并两个有序数组(双指针遍历)上
27. 移除元素 26. 删除有序数组中的重复项 88. 合并两个有序数组(双指针遍历)上
62 1
|
存储 搜索推荐
合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
68 0
|
存储 算法 PHP
PHPHashtable 如何优化数组查找和排序
PHP 是一种高度流行的编程语言,被广泛用于web开发。它有很多的优点,例如易于学习、跨平台、简单易用的语法等等。而在 PHP 中,数组是一种非常常用的数据结构,它可以存储一组有序的数据,方便我们进行各种操作。
66 0
27. 移除元素 26. 删除有序数组中的重复项 88. 合并两个有序数组(双指针遍历)下
27. 移除元素 26. 删除有序数组中的重复项 88. 合并两个有序数组(双指针遍历)下
77 0