首页 > 其他分享 >数组去重、交集、归并

数组去重、交集、归并

时间:2023-03-07 13:44:06浏览次数:35  
标签:map 归并 return 交集 arr length let result 数组

去重

简单结构

let arr = [1,2,3,5,3,5,2,1]

Set 去重

const newArr1 = [...new Set(arr)]
//或
const newArr2 = Array.from(new Set(arr))

indexOf 去重

const newArr = arr.filter((item, index) => arr.indexOf(item) === index)
//或
function unique(arr) {
  return arr.map((ele, index) => {
    if(arr.indexOf(ele) === index) return ele
  })
}
//或
function unique(arr) {
  let result = []
  for(let i = 0; i < arr.length; i++) {
    if(result.indexOf(arr[i] === -1)) result.push(arr[i])
  }
  return result
}

双层for

function unique(arr) {
  let result = []
  for(let i = 0; i< arr.length; i++) {
    let flag = false
    for(let j = i+1; j<arr.length; j++) {
      if(arr[i] === arr[k]) {
        flag = true
        k = arr.length
      }
    }
    if(!flag) result.push(arr[i])
  }
  return result
}

排序法

function unique(arr) {
  let result = []
  let bucket = []
  for(let i = 0; i < arr.length; i++) {
    bucket[arr[i]] = 1
  }

  for(let key in bucket) {
    result.push(Number(key))
  }
  return result
}
//或(使用sort()方法排序,局限性较大,多用于数字数组去重)
function unique7(arr) {
  let result = []
  arr.sort()
  arr.forEach((ele, index) => {
    if(ele !== arr[index + 1]) result.push(ele)
  })
  return result
}

复杂结构

复杂数据结构一般需要判断数组中每一个元素的类型,根据元素的类型,决定是对元素继续比较,所以我们通常会封装一个函数,用来判断元素是否相同

//数组示例
let arr = [
  {id:1, age:23},
  {id:2, age:22},
  {id:4, age:26},
  {id:3, age:20},
  {id:1, age:22},
  {id:4, age:28},
]
//比较元素是否相等的函数
function isEqual(item1, item2)
  //如果是基本数据类型,那就是值的比较;引用类型若===成立,说明地址相同
  if(item1 === item2) return true
  //若===不成立,判断元素类型(Object.prototype.toString.call()可以判断数组 Map Set数据类型)
  let type1 = Object.prototype.toString.call(item1)
  let type2 = Object.prototype.toString.call(item2)
  if(type1 !== type2) return false
  //若类型相同,判断值是否相同
  //Object.keys方法获取可遍历属性,如果参数是对象,返回结果是参数对象自身的(不含继承的)所有可遍历( enumerable )属性的键名(是一个数组);如果参数是字符串或数组,返回索引;
  //Object.values方法返回一个数组,成员是参数对象自身的(不含继承的)所有可遍历属性的键值;
  //Object.entries方法返回一个数组,成员是参数对象自身的(不含继承的)所有可遍历属性的键值对数组;
  switch(type1) {
    case '[object Object]':
      let keys1 = Object.keys(item1)
      let keys2 = Object.keys(item2)
      if(keys1.length !== keys2.length) return false
      for(let i = 0; i<keys1.length; i++) {
        let key = keys1[i]
        if(!isEqual(item1[key],item2[key])) return false
      }
      break;
    case '[object Map]':
    case '[object Set]':
      item1 = Array.from(item1)
      item2 = Array.from(item2)
    case '[object Array]':
      if(item1.length !== item2.length) return false
      for(let i = 0; i < item1.length; i++) {
        if(!isEqual(item1[i], item2[i])) return false
      }
      break
    default:break
  }
  return true
}

循环法

function unique(arr) {
  let result = []
  for(let i= 0; i< arr.length; i++) {
    let flag = true
    for(let j=0; j< result.length; j++) {
      flag = isEqual(arr[i] ,result[j])
      if(!flag) break
    }
    if(flag) result.push(arr[i])
  }
  return result
}

标记版

function unique(arr) {
  let result = []
  //使用Map标记(也可使用WeakMap());
  let cache = new Map()
  for(let i= 0; i< arr.length; i++) {
    if(!cache.has(arr[i])) {
      let flag = true
      //基本类型直接push,引用类型调用上面的isEqual()函数判断
      if(typeof arr[i] === 'object') {
        for (let j = 0; j< result.length; j++){
          flag = !isEqual(arr[i], result[j])
          if(!flag) break
        }
      }
      if(flag) {
        result.pusj(arr[i])
        cache.set(arr[i], true)
      }
    }
  }
  return result
}

交集

  • 交集:两个数组arr1,arr2,找出他们共同的元素(相交的部分);
  • 并集:arr1 -交集 + arr2 -交集 = 并集;
  • 差集:arr1 -交集 = 差集;

综上,我们只要能得到三者其中一个就可以算出另外两个,本篇以交集为例;

双层循环

function intersetction(arr1, arr2) {
  let flag = {}
  let result = []
  for(let i = 0; i< arr1.length; i++) {
    let item = arr1[i]
    for(let j = 0; j< arr2.length; j++) {
      if (item === arr2[j] && !flag[j]) {
        result.push(item)
        flag[j] = true
        break;
      }
    }
  }
  return result
}

Map标记

  • ( 若元素值有引用数据类型可能会出错,因为普通对象没有遍历器( Iterator )接口,无法遍历访问;
function intersection(arr1, arr2) {
  let result = []
  let map = new Map()
  for(let i = 0; i< arr1.length; i++) {1
    if(map.has(arr1[i])) map.set(arr1[i], map.get(arr1[i]+1))
    else map.set(arr1[i], 1)
  }
  for(let i = 0; i< arr2.length; i++) {
    if(map.has(arr2[i])) {
      result.push(arr2[i])
      map.set(arr2[i], map.get(arr2[i]) - 1)
    }
  }
  return result
}

归并

  • 对象类型的数组,找数组中具有相同id的对象,把他们归在一起;
function sameId(data) {
  let result = []
  let map = new Map()
  data.forEach((ele, i) => {
    map.set({id:ele.id},ele)
  })
  data.forEach((item, index) => {
    let tempArr = []
    let res = [...map].filter(([key, value]) => {
      if(key.id === item.id){
        tempArr.push(value)
        map.delete(key)
      }
    })
   if(tempArr.length) {
    result.push(tempArr)
   }
  })
}

标签:map,归并,return,交集,arr,length,let,result,数组
From: https://www.cnblogs.com/rain111/p/17187858.html

相关文章

  • 05、函数传递多维数组
    第一种方法必须使用5来限制参数类型是int[5],另一个参数可以指定voidprint(intm[][5],intdim1){for(inti=0;i!=dim1;i++){for(intj=0;j!=5;j++){......
  • C字符数组和字符指针
    constchar*string="abcd";charstring[]="abcd";第一种称为字符串常量,字符串存储在常量区,由字符指针进行访问,但是不能够修改第二种是字符串数组,相当于创......
  • 连续子数组的最大和【剑指Offer】
    连续子数组的最大和输入一个非空整型数组,数组里的数可能为正,也可能为负。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为......
  • 返回一个整数数组中最大子数组的和
    1.题目:返回一个整数数组中最大数组的和2.要求:(1)输入一个整数数组,数组里有正数也有负数。(2)数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和......
  • 课堂练习:最大子数组
    参考了一篇学长的博客,受益匪浅,通过不断累加,当和变成负数归零从一个数开始加,之前的结果保存到max,每一次的结果都跟max对比,保证只要不低于0的负数都可以加进来1pu......
  • 求数组中的最大子数组的和--相关测试
    测试一:在普通的数组里面求最大子数组的和首先给出一个普通数组的定义,然后循环遍历,为数组的n个元素赋值;然后再根据a[i]+a[i-1]>a[i]的条件是否成立,来进行加和运算,然后赋值......
  • 209. 长度最小的子数组 (Medium)
    问题描述209.长度最小的子数组(Medium)给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其和≥target的长度最小的连续子数组[numsₗ,num......
  • 求一个数组中所有子数组和的最大值
    importdao.StuMapper;importorg.junit.Test;importorg.springframework.context.ApplicationContext;importorg.springframework.context.support.ClassPathXmlAppl......
  • js一维数组转二维数组
    利用数组的splice方法进行转换1.封装函数  2.使用方法 ......
  • 算法与数据结构——整数数组求最大子数组
    题目:输入一个整型数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。代码:......