搜索

首页  >  问答  >  正文

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啊,所以就开始想到底怎么返回这个被修改之后的数组,但是看了好多的数组去重的文章,还是没找到答案,求大佬指导一波!!!!

欧阳克欧阳克2793 天前619

全部回复(3)我来回复

  • 阿神

    阿神2017-06-12 09:30:19

    就地去重的思路很简单

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

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

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

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

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

    回复
    0
  • 怪我咯

    怪我咯2017-06-12 09:30:19

    这道题不是单纯的数组去重,这个数组是排好序的,这就跟乱序数组去重是不一样的。

    有序数组去重,相同元素会分布在一起,所以只需要在遍历过程中判断后一个元素跟前一个元素是否相同,来进行去重。

    这道题当时我的 AC

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

    回复
    0
  • 高洛峰

    高洛峰2017-06-12 09:30:19

    const removeDuplicates=arr=>Array.from(new Set(arr))

    回复
    0
  • 取消回复