腾讯：不产生新数组，删除数组里的重复元素

数组去重的方式有很多，我们可以使用 Set 去重、filter 过滤等，详见携程&蘑菇街&bilibili：手写数组去重、扁平化函数，但三种解法（Set、filter、reducer）都产生了新数组：

MDN ： filter() 方法创建一个新数组, 其包含通过所提供函数实现的测试的所有元素。

那么我们如何在不产生性数组的情况下删除数组中的重复元素喃？

方式一：排序去重

MDN：sort() 方法用原地算法对数组的元素进行排序，并返回数组。默认排序顺序是在将元素转换为字符串，然后比较它们的UTF-16代码单元值序列时构建的

const removeDuplicates = (nums) => {
    // 原地排序
    nums.sort()
    // 去重
    let len = 1
    for (let i = 1; i < nums.length; i++)
        if (nums[i] != nums[i-1]) nums[len++] = nums[i];
    // 删除重复项
    nums.splice(len)
    return nums
}

// 测试
removeDuplicates([1, 2, 3, 1, 3])
// [1, 2, 3]

方式二：优化

const removeDuplicates = (nums) => {
    let len = nums.length - 1
    for(let i = len; i>=0; i--) {
        if(nums.indexOf(nums[i]) != i) {
            nums[i] = nums[len --]
        }
    }
    // 删除重复项
    nums.splice(len+1)
    return nums
}
// 测试
removeDuplicates([1, 2, 3, 1, 3])
// [1, 2, 3]

function setArr(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        arr.splice(j, 1);
        j--
      }
    }
  }
  return arr
}

function setArr(arr) {
  for(let i = 0;i<arr.length;i++){
    if(arr.indexOf(arr[i])!==i){
      arr.splice(i,1);
      i--
    }
  }
  return arr
}

let uniqueArr=function uniqueArr(arr){

	let map={};
	
	let len = arr.length-1;
	
	while(len>=0){
		let item = arr[len];
		if(map[item]){
			arr.splice(len,1)
		}else{
			map[item]=true;
		}
		len--;
	}
	
	return arr;

}

function setArr(arr, map = new Map()) {
  let idx = arr.length - 1;
  while (idx >= 0) {
    if (map.get(arr[idx])) {
      arr.splice(idx, 1)
    } else {
      map.set(arr[idx], true)
    }
    idx--;
  }
  return arr
}

const arr = [1, 2, 3, 1, 3, 5, 5, 5, 5, 5, 5];

function removeDuplicates(list) {
  const map = {};
  for (let i = 0; i < list.length; i += 1) {
    const item = list[i];
    if (!map[item]) {
      map[item] = true;
    } else {
      list.splice(i, 1);
      i -= 1;
    }
  }
}

removeDuplicates(arr);
console.log(arr); // [1, 2, 3, 5];

const setArr = arr => {

// 利用对象属性唯一性
let obj = {}
for (let i = 0; i < arr.length; i++) {
if (obj[arr[i]]) {
arr.splice(i, 1);
i--
} else {
obj[arr[i]] = arr[i]
}
}

return arr

}

// 双指针
const removeDuplicates = (nums) => {
nums.sort((a, b) => a - b);

let slow = -1;
for (let i = 0, len = nums.length; i < len; i++) {
if (nums[slow] !== nums[i]) {
nums[++slow] = nums[i];
}
}

return nums.slice(0, slow + 1);
};

Navigation Menu

Repository navigation

腾讯：不产生新数组，删除数组里的重复元素 #135

方式一：排序去重

方式二：优化

const setArr = arr => {

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

腾讯：不产生新数组，删除数组里的重复元素 #135

Description

方式一：排序去重

方式二：优化

Activity

fxwing commented on Dec 7, 2020

fxwing commented on Dec 7, 2020

lyvvq9296 commented on Dec 7, 2020

fxwing commented on Dec 7, 2020

z253573760 commented on Feb 2, 2021

XW666 commented on Apr 20, 2021

const setArr = arr => {

zixiaoyan12 commented on May 11, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions