Leecode - 从数组中删除重复项

2019-06-12 admin

原文地址: https://www.luoyangfu.com/art…

题目

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,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。

你不需要考虑数组中超出新长度后面的元素。 说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

思路

根据题目说明:

  1. 排序的数组 -> 数组是有序的
  2. 原地删除重复数组 -> 不能移除
  3. 每个元素只出现一次 -> 时间复杂度O(n)
  4. 不能使用额外的数组空间 -> 不能复制元素
  5. 不用考虑数组中超出长度的数据 -> 和第2条对应,把要移除的元素放到后面

我们需要在 时间复杂度为O(n) 情况下为一个有序的数组做一个删除, 我们使用一个计数变量 i = 0 来标记当前数组不重复的数据的,但是这个时候我们需要 原地删除 数组,这个时候就需要重复的数据放到后面,这样返回的数据就可以保持在前面 i 个数据是不重复的。既然需要和后面元素交换,数组交换需要两个下表,我们这里再采用另外一个 计数变量j 来表示作为当前数组遍历计数变量. 根据上述描述,我们使用的方法也称之为双指针法. 这里i 称之为慢指针, j 称之为快指针

双指针,顾名思义,就是利用两个指针去遍历数组,一般来说,遍历数组采用的是单指针(index)去遍历,两个指针一般是在有序数组中使用,一个放首,一个放尾,同时向中间遍历,直到两个指针相交,完成遍历,时间复杂度也是O(n)。

解决方法

根据解决思路我们这里使用 javascript 语法来开发:

function removeDuplicates(arr) {

    if(!Array.isArray(nums) || !nums.length) return 0;

    if(nums.length < 2) return 1;

    var i = 0;

    for(var j = 1; j < nums.length; j ++) {

        if(nums[i] !== nums[j]) {
            i ++; 
            nums[i] = nums[j]
        }
    }

    return ++i;
}

上面代码有两点要解释的,判断 nums[i] !== nums[j] 这里,当他们不相等的时候进行 ij 的位置交换, 当相同的时候j 就跳过相同的元素的, i++ 就在不同的下一个元素进行交换。 在最后返回 ++i 这里,以为 i 是从0开始,因此长度需要+1.

[转载]原文链接:https://segmentfault.com/a/1190000019455258

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-67115.html

文章标题:Leecode - 从数组中删除重复项

相关文章
jQuery中DOM树操作之使用反向插入方法实例分析
本文实例讲述了jQuery中DOM树操作之使用反向插入方法。分享给大家供大家参考。具体分析如下: 使用反向插入方法 这里我们先把创建的内容插人到元素前面,然后再把同一个元素插人到文档 中的另一个位置。通常,当在jQuery中操作元素时,利用...
2015-11-13
可以从CSS框架中借鉴到什么
现在很多人会使用 CSS 框架进行快速建站。   那 CSS 框架是什么呢,它通常是一些 CSS 文件的集合,这些文件包括基本布局、表单样式、网格、简单组件、以及样式重置。使用 CSS 框架大大降低工作成本进行快速建站。   当然对于一些大...
2016-03-11
JS中的语音合成——Speech Synthesis API
JS中的语音合成——Speech Synthesis API 简介 HTML5中和Web Speech相关的API实际上有两类,一类是“语音识别(Speech Recognition)”,另外一个就是“语音合成(Speech Synthes...
2018-05-17
7个让JavaScript变得更好的注意事项
随着浏览器性能提高,伴随着新的HTML5的编程接口的稳步采用,网页上的JavaScript的音量在逐渐增加。然而,一个写得不好的程序编码却拥有着打破整个网站,让用户为之沮丧和驱赶潜在客户的潜力。 开发人员必须使用所有供他们任意使用的工具和技...
2015-11-12
从 Node.js 分裂出 Io.js 事件看开源软件谁做主
Node.js 作为服务器编程语言的后起之秀,常用来构建和运行 Web 应用,近日却爆出其社区出现分裂。由于对官方运营商 Joyent 公司在 Node.js 管理上的长期不满,多位核心开发者另立门户,创建了分支 Io.js。从 GitHu...
2015-11-12
jQuery中DOM树操作之复制元素的方法
本文实例讲述了jQuery中DOM树操作之复制元素的方法。分享给大家供大家参考。具体分析如下: 复制元素 前面提到的操作包括:插人新创建的元素、将元素从文档中的一个位置移动 到另一个位置,以及通过新元素来包装已有的元素。可是,有时候也会用到...
2015-11-13
从 JavaScript 到 TypeScript - 声明类型
从 JavaScript 语法改写为 TypeScript 语法,有两个关键点,一点是类成员变量 (Field) 需要声明,另一点是要为各种东西 (变量、参数、函数 / 方法等) 声明类型。而这两个点直接引出了两个关键性的问题,有哪些类型?...
2017-06-05
在 Microsoft Azure 中使用 MEAN 堆栈基于开放数据协议
网络开发人员通常构建伟大的应用程序在客户端使用JavaScript和ASP(c#或Visual Basic . NET)在服务器端。 但是如果你能使用一个共同的语言来构建应用程序的所有层堆栈,从浏览器和服务器端业务处理服务层,甚至在数据库查...
2015-11-12
关于Ajax应用开发需要注意的事项
接触Ajax,那时候的Ajax支持还不是很好,都要涉及底层,没有现成的框架给你调用。现在把常见的问题列举如下。 [b]1、编码问题[/b] 注意AJAX要取的文件是UTF-8编码的。GB2312编码传回BROWSE后中文会乱码。如果用VBS...
2015-11-11
JS中Select下拉列表类(支持输入模糊查询)功能
下面给大家分享一段代码关于select下拉列表类支持输入模糊查询功能的实现代码,具体代码如下所示: &lt;span style=&quot;font-size:14px;&quot;&gt; &lt;HTML&gt; &lt...
2017-03-06
回到顶部