① Remove Duplicates from Sorted Array

算法题目

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

给定一个已排序的数组,在适当的位置删除重复项,使每个元素只出现一次,并返回新的长度。
不要为另一个数组分配额外的空间,必须在内存不变的情况下就地分配。

解决方案:

因为是已经排序的数组,通过两个变量遍历整个数组,第一个变量slow从0开始用于存储非重复的数据,第二个变量fast从1开始编辑剩余所有数据,遍历过程中将所有不重复的数据依次记录到++slow中,最终形成了剔除重复元素的数据并完成了数据量slow+1记录!

算法原理


20160916210024639.gif

JavaScript代码实现:

function removeDuplicates(arr) {
    if(arr.length <= 0){
        return 0
    }
    let slow = 0
    for(let fast = 1; fast < arr.length; fast ++) {
        if(arr[slow] != arr[fast]) {  // 1, 1, 2
            arr[++slow] = arr[fast]
        }
    }
    return slow + 1
}

let a = [1, 1, 2];
console.log(removeDuplicates(a), a) // 2, [1, 2, 2]
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容