javascript - js,刷leetcode的时候突然脑洞的一个问题

问题描述

问 题

当时刷的是一道数组去重的题
题干https://leetcode.com/problems...
当时刷的时候也accepted了，但是突然想到了一个问题，到底怎么样才能在不开新的数组的情况之下对原数组完成去重而且返回修改之后的数组？？
下面是自己通过的代码

var removeDuplicates = function(nums) {
    if(nums === null || nums.length === 0) return 0;
    if(nums.length == 1) return 1;
    var count = 0;
    for(var i = 1 ; i < nums.length ; i++){
        if(nums[count] != nums[i]){
            count++;
            nums[count] = nums[i];
        }
    }    
    return ++count;
};

开始的时候想到的是最后返回nums.length，但是仔细一想，这不是在开玩笑嘛，这样写返回的肯定还是原来未经改变的nums啊，所以就开始想到底怎么返回这个被修改之后的数组，但是看了好多的数组去重的文章，还是没找到答案，求大佬指导一波！！！！

解决方案

就地去重的思路很简单

1. 建立一个以每个数组元素为 key 的 hash 对象

2. 每个元素通过 hash 判断其是否已经存在与数组中

3. 如存在，将该元素删除

4. 遍历完成后，移动数组元素，填补空位

由于移动数组元素是一个高耗操作（例如 N 长数组被均匀挖掉 N/2 个空，那么这时由后往前移动元素的时间复杂度能到 N^2 的水平），并且这个算法不符合当前的 immutable 趋势，因此这种做法是吃力不讨好的，一般场景下也没有必要去做。

这篇关于javascript - js,刷leetcode的时候突然脑洞的一个问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！