Open zpzxgcr opened 5 years ago
其实题目包含三个要求:1.扁平化,2.去重,3.排序,如果利用ES6的特性,依次利用flat(Infinity)打平,Set去重和sort排序就好了。 最近学习数据结构觉得开始偏爱非递归写法,讲真从栈调用上非递归写法真的感觉比递归要有意思的多
function foo(arr) {
let s = new Set();
while(arr.length > 0) {
let item = arr.shift();
if (Array.isArray(item)) {
arr.push(...item)
} else {
s.add(item)
}
}
return [...s].sort((item1, item2) => item1 - item2);
}
\<\?php class SORT {
public $result=[];
public function to_array_one($arr){
if (is_array($arr)) {
foreach ($arr as $value) {
if (is_array($value)) {
$this->to_array_one($value);
}else{
$this->result[$value]=$value;
}
}
}
}
public function array_sort_asc($arr){
$array=[];
foreach ($arr as $value) {
$array[]=$value;
}
unset($arr);
$data = '';
$count=count($array);
for ($i=0; $i < $count ; $i++) {
for ($j=$i; $j < $count-1; $j++) {
if ($array[$i]>$array[$j+1]) {
$data = $array[$i];
$array[$i]=$array[$j+1];
$array[$j+1]=$data;
}
}
}
return $array;
}
}
$a=[ [1, 2, 2], [3, 14, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [4] ] ] ], 10];
$obj=new SORT; $obj->to_array_one($a); $array=$obj->array_sort_asc($obj->result);
print_r($array);
//非常丑陋,轻喷呀
function ss(arr){
//扁平
function handleArr(arr){
if(Array.isArray(arr)){
var b = [];
arr.reduce(function(addarr,next){
b = b.concat(handleArr(next))
},b)
return b
}
else{
return arr
}
}
//排序
var _arr = handleArr(arr).sort(function(a,b){return a-b});
//去重
for(let i=0;i<_arr.length;i++){
if(_arr.indexOf(_arr[i]) !== i){
_arr.splice(i,1);
i--;
}
}
return _arr;
}
var arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10];
function flat(ary, result = [], layer = 0) {
for (let i = 0, j; (j = ary[i++]); ) {
j.length ? flat(j, result, layer + 1) : (result[+j] = j);
}
if (!layer) return result.filter(Boolean);
}
flat(arr);
(14) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
var arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10]; function flat(ary, result = [], layer = 0) { for (let i = 0, j; (j = ary[i++]); ) { j.length ? flat(j, result, layer + 1) : (result[+j] = j); } if (!layer) return result.filter(Boolean); } flat(arr); (14) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
为啥这里这个for循环我都看晕了。。。这个循环没有终止条件吗?
var arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10]; function flat(ary, result = [], layer = 0) { for (let i = 0, j; (j = ary[i++]); ) { j.length ? flat(j, result, layer + 1) : (result[+j] = j); } if (!layer) return result.filter(Boolean); } flat(arr); (14) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
为啥这里这个for循环我都看晕了。。。这个循环没有终止条件吗?
(j = ary[i++]), 返回 ary[i++],超出数组边界的时候,返回 undefined,为 false,终止循环。
var arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10]; function flat(ary, result = [], layer = 0) { for (let i = 0, j; (j = ary[i++]); ) { j.length ? flat(j, result, layer + 1) : (result[+j] = j); } if (!layer) return result.filter(Boolean); } flat(arr); (14) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
为啥这里这个for循环我都看晕了。。。这个循环没有终止条件吗?
(j = ary[i++]), 返回 ary[i++],超出数组边界的时候,返回 undefined,为 false,终止循环。
万分感谢您的回复和解答!!
[... new Set(arr.flat(Infinity))].sort((a, b) => a - b)
这个题目是不是手写算法题吗?前排的答案不是很赞同
[ ...new Set( arr.flat(Infinity) ) ].sort( (a,b) =>a-b )
const arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10];
const flatNumberArr = (arr: any[]) => {
return arr.reduce((a, b) => {
if (Array.isArray(b)) return [...a, ...flatNumberArr(b)];
return [...a, b]
},[])
}
const flatArr = flatNumberArr(arr);
const uniqueArr = new Set(flatArr)
const finalArr = Array.from(uniqueArr).sort((a:number,b:number)=>a-b);
console.log(finalArr);
const arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10];
let newArr = [];
function jie(arr) {
if (!(arr && arr.length)) {
return;
}
arr.forEach(element => {
if (element) {
if (element.length) {
jie(element);
} else {
newArr = newArr.filter(i => i !== element);
newArr.push(element);
}
}
});
}
jie(arr);
arr.sort((a, b) => a - b);
let newArr = [...new Set(arr.flat(Infinity))].sort((a,b) => a-b )
console.time('a')
let arr = [[1,2,2],[3,4,5,5],[6,7,8,9,[11,12,[12,13,[14,[19,[20]]]]]],10];
let flatten = [];
let unique = [];
function flattenfn(arr){
for(let i = 0; i < arr.length; i++){
if(Array.isArray(arr[i])){
flattenfn(arr[i])
}else{
flatten.push(arr[i])
}
}
}
function uniquefn(flatten){
for (let i = 0; i < flatten.length; i++) {
if(!unique.includes(flatten[i])){
unique.push(flatten[i])
}
}
}
function quicksort(arr){
if(arr.length < 1){
return arr;
}
let temp = arr[0];
let left = [];
let right = [];
for (let i = 1; i < arr.length; i++) {
if(arr[i] < temp){
left.push(arr[i])
}else{
right.push(arr[i])
}
}
return quicksort(left).concat(temp,quicksort(right))
}
flattenfn(arr)
uniquefn(flatten)
result = quicksort(unique)
console.timeEnd('a')
console.log(result);
var util = {
array2one: function ({ arr = [], isDistinct = false, isSort = false, initArr = [] }) {
arr && arr.forEach(item => {
Array.isArray(item) && this.array2one({ arr: item, initArr, isDistinct }) || (isDistinct ? initArr.indexOf(item) == -1 && initArr.push(item) : initArr.push(item));
})
return isSort&&initArr.sort((a,b)=>a-b)||initArr;
}
};
var s = util.array2one({ arr, isDistinct: true,isSort:true });
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ]
Array.from(new Set(arr.toString().split(","))).sort((a,b) => a-b)
// es6 var es6Arr = Array.from(new Set(arr.flat(4))).sort((a,b)=>{return a- b}); console.log(es6Arr);
// es5 var newArr = []; function jie(_arr) { function typeArr(_obj) { return Object.prototype.toString.call(_obj).indexOf('Array') > -1 } if (typeArr(_arr)) { for (let index = 0; index < _arr.length; index++) { const element = _arr[index]; if (typeArr(element)) { jie(element) } else { newArr.indexOf(element) == -1 ? newArr.push(element) : ''; } }
}
} jie(arr) newArr = newArr.sort((a, b) => {return a-b}) console.log(newArr);
let z = A => [...new Set([].concat(...A.map(x => Array.isArray(x) ? z(x) : x)))].sort((a, b) => a - b)
function bp(arr,a=[]){
var flag = 1;
if(arr.length>0 && typeof arr=="object"){
for(let i = 0;i<arr.length;i++){
if(typeof arr[i]=="object"){
a=a.concat(arr[i]);
flag=0
}else{
a.push(arr[i])
}
}
}else{
a.push(arr)
}
if(flag){
let t = [...new Set(a)];
t.sort((a, b) => a - b)
return t;
}else{
return bp(a,[]);
}
}
这是一道算法题,主要考察三种算法:数组扁平化
、数组去重
、排序
,所以楼上的回答都没有答到点上,我们需要做的是在数组扁平化同时进行数组去重和排序,兼顾时间与空间复杂度。
我的思路是在进行数组扁平化的同时,进行重复判断和插入排序
,重复判断无非就是进行元素查找的过程,故可使用二分查找
。二分查找
与插入排序
结合即为二分插入排序算法
。但是这个思路并不正确。
数组扁平化操作即为取出一个数组项,判断是否为数组,如果为非数组的话则插入
到结果数组中,这个插入的过程可以做到去重
和排序
。这样就能够保证我们没插入一个非数组的数组项时结果数组是排序与去重好的。
function flatArrayWithUniqueAndSort(arr) {
const resultArr = []
while (arr.length) {
const item = arr.shift()
if (Array.isArray(item)) {
arr.push(...item)
} else {
if (!resultArr.length) {
resultArr.push(item)
} else {
for (let i = resultArr.length - 1; i >= -1; i--) {
if (item === resultArr[i]) break
if (item > resultArr[i] || resultArr[i] === undefined) {
resultArr.splice(i + 1, 0, item)
break
}
}
}
}
}
return resultArr
}
[...new Set(arr.toString().split(',').map(item => parseInt(item)))].sort((a, b) => a - b)
我的思路是先把数组拍平 定义一个obj用key来记录数组中的每一项,然后直接forin obj(obj中的索引会按照从小到大排列,所以直接push到数组中就可以) var arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [100, 12, [12, 13, [14] ] ] ], 10] const flatDeep = (arr) => { let obj = {} const deep = (arr) => { for (let i = 0; i < arr.length; i++) { if (arr[i] instanceof Array) { deep(arr[i]) } else { if (obj[arr[i]]) { obj[arr[i]]++ } else { obj[arr[i]] = 1 } } } } deep(arr)
let sortArr = [] for (const item in obj) { sortArr.push(+item) } return sortArr }
拍平:
const deepFlatten = arr => [].concat(...arr.map(v => (Array.isArray(v) ? deepFlatten(v) : v)));
用toString会改变数组里面的原始数据,应该会是扣分项。
toString 好像并不会改变原数组的
Array.prototype.flat 还是一个proposal,虽然chrome和firefox支持了(但都才支持不久),还是不建议使用,等到变成正式的规范了再用会更好吧
let map = []
let result = []
function main (array) {
for (let i = 0; i < array.length; i++) {
if (Array.isArray(array[i])) {
main(array[i])
} else {
map[array[i]] = 1
}
}
}
main([ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10])
for (let i = 0; i < map.length; i++) {
if (map[i]) {
result.push(i)
}
}
console.log(result.join(','))
Array.form(new set(arr.flat()).sort((a,b)=>a-b))
[...new Set(arr.join().split(','))].sort((a, b) => a - b)
原题中的Infinity是用来干什么的 扁平化的层级 不知道几层 就无穷大
function handleArr (arr) {
if (Object.prototype.toString.call(arr) != '[object Array]') return arr;
let newarr = [];
for(let i =0; i<arr.length; i++) {
if (Object.prototype.toString.call(arr[i]) == '[object Array]') {
newarr = newarr.concat(handleArr(arr[i]))
} else {
// 去重
if (newarr.indexOf(arr[i]) == -1) {
newarr.push(arr[i])
}
}
}
//排序
return newarr.sort((a, b) => a-b)
}
Array.from(new Set(arr.flat(Infinity))).sort((a,b)=>{ return a-b})
这操作。。
我的是这样操作的
Array.from(new Set(JSON.parse('['+arr.toString()+']'))).sort((a,b)=>a-b)
function flat (arr, n=[]) {
arr.forEach((v) => {
if(v instanceof Array) {
flat(v, n)
} else {
n.push(v)
}
})
return n
}
new Set(flat(arr).sort((a,b)=> {return a-b}))
// 1 拍平 console.log(arr) let newArr = arr.flat(4); console.log(newArr,'排序'); // 2 去重 let noRepeat = Array.from(new Set(newArr)); console.log(noRepeat,'去重') // 3 排序 let sort = noRepeat.sort((a, b) => { return a - b }) console.log(sort,'排序')
这题其实水是比较深的, 如果单从解该题的角度考虑。其实可以省略 sort 的步骤:
const flatify = (ary) => {
return ary.flat(1)
}
const weftReducation = (ary) => {
let tempAry = flatify(ary)
const ret = []
for (let i = 0; i < tempAry.length; i++) {
if (Array.isArray(tempAry[i])) {
[].push.apply(tempAry, flatify(tempAry[i]))
} else {
ret.push(tempAry[i])
}
}
return [...new Set(ret)]
}
var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];
Array.from(new Set(arr.toString().split(','))).map(i => parseInt(i)).sort((a, b) => a-b)
偷工减料~
const splice = Array.prototype.splice;
const list = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10];
testListFlat(list)
// ===================================
// result: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
// listFlat1: 0.65087890625ms 、0.88916015625ms、0.625ms、0.77294921875ms、0.598388671875ms、0.5771484375ms
// result: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
// listFlat2: 0.424072265625ms、0.77392578125ms、0.4208984375ms、5.580078125ms、0.453857421875ms、0.39013671875ms
// result: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
// listFlat3: 0.390869140625ms、0.550048828125ms、0.39794921875ms、0.432861328125ms、0.446044921875ms、0.34375ms
function testListFlat(list) {
console.time('listFlat1')
console.log(listFlat1(list))
console.timeEnd('listFlat1')
console.time('listFlat2')
console.log(listFlat2(list))
console.timeEnd('listFlat2')
console.time('listFlat3')
console.log(listFlat3(list))
console.timeEnd('listFlat3')
}
function listFlat1(list = []) {
const _list = list.slice();
const _flatList = []
for (let i = 0; i < _list.length; ) {
const item = _list[i];
if (!Array.isArray(item)) {
_flatList.push(item);
i++;
} else {
splice.apply(_list, [i, 1].concat(item))
}
}
return [...new Set(_flatList)].sort((a,b)=>a - b)
}
function listFlat2(list = []) {
return [...new Set(list.join(',').split(',').map(item => Number(item)))].sort((a,b) => a - b)
}
function listFlat3(list = []) {
return [...new Set(list.flat(4).sort((a,b) => a - b))]
}
简单汇总一下扁平化方法吧:
// 1、新方法Array.prototype.flat,兼容性较差
arr.flat(Infinity)
// 2、Array.prototype.reduce
function flatten(arr) {
return arr.reduce((total, val) => {
return total.concat(Array.isArray(val) ? flatten(val) : val);
}, []);
}
arr = flatten(arr);
// 3、toString或join
arr = arr.toString().split(',').map(v=>Number(v));
arr = arr.join().split(',').map(v=>Number(v));
// 4、基础的递归
map或[...arr],类似于上面的arr.some和Array.isArray()
// 最后:统一去重排序
Array.from(new Set(arr).sort((a,b)=>a-b)
Array.from(new Set(arr.toString().split(",").map(item => +item))).sort((a, b) => {return a - b});
arr.toString().split(',').filter((el, index, array)=>{ return index === array.indexOf(el) }).sort((a, b)=>return a-b)
arr.toString().split(',') 扁平化 filter + indexOf 去重 sort 是排序
const arr =[ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]. [...new Set(arr.toString().split(','))].sort((a,b)=>a-b)
const arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]; Array.from(new Set(arr.toString().split(',').sort((x,y)=>{return x-y}).map(item=>+item)))
[...new Set(arr.flat(100))].sort((a,b) => a-b)
[...new Set(arr.flat(100))].sort((a,b) => a-b)
flat(100)??
[...new Set(arr.flat(4))].sort((a, b) => a-b)
[ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10].flat(4).filter((item, index, array) => array.lastIndexOf(item) == index).sort((a,b) => a-b)
[...new Set(arr.toString().split(","))].sort((a, b) => a - b)
const flat = (arr, list = []) => {
if (!Array.isArray(arr)) return list.push(arr)
arr.forEach(item => flat(item, list))
return list
}
const distinctAndSort = arr => [...new Set(arr)].sort((a, b) => a - b)
distinctAndSort (flat(arr))
function flatAndSort (inArr) {
let result = [];
if (!inArr || !inArr.length) {
return result;
}
const foreach = (arr) => {
arr.forEach((item) => {
if (Array.isArray(item)) {
foreach(item)
} else {
const index = result.findIndex((rItem) => rItem > item);
if (index !== -1) {
if (result[index - 1] !== item) {
result.splice(index, 0, item)
}
} else {
result.push(item)
}
}
});
}
foreach(inArr);
return result;
}
不知道有现成的flat API,自己写了递归。。。
function flatArr(source,target){
let clonedArr = target || []
source.forEach(item=>{
if(item instanceof Array){
flatArr(item,clonedArr)
}else{
clonedArr.push(item)
}
})
return clonedArr
}
function sortArr(arr){
return [...new Set(arr)].sort((a,b)=>a-b)
}
[...new Set(arr.toString().split(',').sort((a, b) =>a-b).map(Number))]
Array.from(new Set(arr.flat(Infinity))).sort((a,b)=>{ return a-b})