来自：AnnatarHe's blog
链接：https://annatarhe.github.io/2016/12/21/some-diff-filter-method.html
最近写了一道数组去重的题，手抖，紧张，没写好。后来写了一会儿觉得还挺有意义的。现在做一下记录
Test case
测试用例如下
import test from 'ava' import unique from '../src/unique' test('[1,1,2] should return [1, 2]', t => { t.plan(3) const src = [1,1,2] const result = unique(src) t.is(result.length, 2) t.is(result[0], 1) t.is(result[1], 2) }) test('[1, 1, "1"] should return [1, "1"]', t => { t.plan(4) const src = [1, 1, '1'] const result = unique(src) t.is(result.length, 2) t.is(result.indexOf(1), 0) t.is(typeof result[1], 'string') t.is(result.indexOf('1'), 1) }) test('deep unique', t => { const src = [1, 1, "1", false, false, true, {hello: 'world'}, [1, 2], [1, 2]] const result = unique(src) t.is(result.length, 6) }) test('deep unique', t => { const src = [1, 1, "1", false, false, true, {hello: 'world'}, [1, 2], [1, 2], {hello: 'world'}] const result = unique(src) t.is(result.length, 7) })
简单去重的几种方法
暂时先只看数组中存number的去重方法：
最粗暴的是这种，利用Set不能有重复数据的特性做
const unique = arr => Array.from(new Set(arr))
正常思路如下，维护一个暂存数组，将数据存进去
function unique(arr) { let temp = [] for (let i = 0; i if (temp.indexOf(arr[i]) === -1) { temp.push(arr[i]) } } return temp }
reduce做去重(下面有参考链接)，意思是每次往前一个数组中塞数据，其实就是上面正常思路的去中间变量版
function unique(arr) { let temp = [] for (let i = 0; i if (temp.indexOf(arr[i]) === -1) { temp.push(arr[i]) } } return temp }function uniqueByReduce(arr) { return arr.reduce((prev, next) => { if (prev.indexOf(next) === -1) { prev.push(next) } return prev }, []) }
这个时候基本int型数据都没什么问题了。
但是我上面测试用例中最后一个用例明显是无法通过的。那么就需要更多的判断
更复杂的去重
先贴代码:
function unique(arr) { let temp = [] for (let i = 0; i if (typeof arr[i] === 'object' && (! Array.isArray(arr[i]))) { if (! objects.contains(temp, arr[i])) { temp.push(arr[i]) } }else if (Array.isArray(arr[i])) { if (! arrays.contains(temp, arr[i])) { temp.push(arr[i]) } }else { if (temp.indexOf(arr[i]) === -1) { temp.push(arr[i]) } } } return temp }
意思是在推进去的时候多做一些判断，主要是对Object和Array的判定。
其中有objects.contains和arrays.contains两个方法做判定工作。其实现分别如下
// array.js export function equals(src, dist) { if ((! Array.isArray(src)) || (! Array.isArray(dist))) { throw new Error('请传入Array哦~??') } if (src.length !== dist.length) { return false } for (let index = 0; index if (Array.isArray(src[index]) && Array.isArray(dist[index])) { if (! equals(src[index], dist[index])) { return false } } else { if (src[index] !== dist[index]) { return false } } } return true } export function contains(father, child) { let flags = [] father.forEach(item => { if (Array.isArray(item)) { if (equals(item, child)) { flags.push(true) } } }) return flags.indexOf(true) !== -1 }
// objects.js function isPlainObj(obj) { return typeof obj === 'object' && (! Array.isArray(obj)) && obj !== null } export function equals(obj1, obj2) { if (Object.keys(obj1).length !== Object.keys(obj2).length) { return false } for (let item in obj1) { // 这里简单判断算了，后面可以更复杂 if (isPlainObj(obj1[item])) { if (isPlainObj(obj2[item])) { if (! equals(obj1[item], obj2[item])) { return false } }else { return false } }else { if (obj1[item] !== obj2[item]) { return false } } } return true } export function contains(father, child) { for (let key in father) { if (isPlainObj(father[key])) { // 因为只给了值，所以得有个中间层 const tempObj = { [key]: father[key] } if (equals(tempObj, child)) { return true } } } return false }
关于array.js和objects.js的测试用例我就不给出了。
反正最后测试都通过了，感觉真好~
References
程序员共读↓↓↓
Java编程精选↓↓↓
更多推荐《年薪百万的程序员都在干什么?》
涵盖：程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等
