关于javascript:JS数组操作扁平化去重排序交集并集差集二分查找峰值位置

35次阅读

共计 4937 个字符,预计需要花费 13 分钟才能阅读完成。

整顿欠缺一下数组相干的操作:
一、对于数组扁平化

1.reduce

// 若值为数组则递归遍历,否则 concat
function flatten(arr) {return arr.reduce((result, item)=> {return result.concat(Array.isArray(item) ? flatten(item) : item);
    }, []);
}
//reduce 是数组的一种办法,它接管一个函数作为累加器,数组中的每个值(从左到右)开始缩减,最终计算为一个值。//reduce 蕴含两个参数:回调函数,传给 total 的初始值

// 求数组的各项值相加的和:arr.reduce((total, item)=> {  // total 为之前的计算结果,item 为数组的各项值
    return total + item;
}, 0);

2.toString & split

// 调用数组的 toString 办法,将数组变为字符串而后再用 split 宰割还原为数组
function flatten(arr) {return arr.toString().split(',').map(function(item) {return Number(item);
    })
}
// 因为 split 宰割后造成的数组的每一项值为字符串,所以须要用一个 map 办法遍历数组将其每一项转换为数值型

3.join & split

// 和下面的 toString 一样,join 也能够将数组转换为字符串
function flatten(arr) {return arr.join(',').split(',').map(function(item) {return parseInt(item);
    })
}
  1. 递归
function flatten(arr) {var res = [];
    arr.map(item => {if(Array.isArray(item)) {res = res.concat(flatten(item));
        } else {res.push(item);
        }
    });
    return res;
}

5. 扩大运算符

//es6 的扩大运算符能将二维数组变为一维
[].concat(...[1, 2, 3, [4, 5]]);  // [1, 2, 3, 4, 5]
// 依据这个后果咱们能够做一个遍历,若 arr 中含有数组则应用一次扩大运算符,直至没有为止。function flatten(arr) {while(arr.some(item=>Array.isArray(item))) {arr = [].concat(...arr);
    }
    return arr;
}

二、数组去重

1. 办法一(Set)
Array.from 办法用于将两类对象转为真正的数组:相似数组的对象(array-like object)和可遍历(iterable)的对象(包含 ES6 新增的数据结构 Set 和 Map)。ES6 提供了新的数据结构 Set。它相似于数组,然而成员的值都是惟一的,没有反复的值;

var duplicate = Array.from(new Set(newArr1))

2、办法二(reduce)

// 通过数组 reduce 办法,利用 indexOf 判断上一次回调返回数组 a 中是否蕴含以后元素 b 的索引,如果不存在,则把 b 元素退出 a 数组,否则间接返回 a。var duplicate1 = newArr1.reduce((a, b) => {if(a.indexOf(b) === -1) {a.push(b)
    }
    return a
}, [])

3、办法三(数组下标去重法)

// 通过数组的过滤 filter 办法,利用 indexOf 获取以后元素 ele 在被过滤数组 farr 中的第一个索引值,如果值与以后索引值 index 相等则返回,如果不相等则过滤。var duplicate2 = newArr1.filter((ele, index, farr) => {return farr.indexOf(ele) === index
})

4、办法四(遍历数组)

// 遍历数组,建设新 duplicate3 数组,利用 indexOf 判断元素是否存在于 duplicate3 新数组中,不存在则 push 到 duplicate3 新数组。var duplicate3 = []
for(var i = 0; i < newArr1.length; i++) {if(duplicate3.indexOf(newArr1[i]) === -1) {duplicate3.push(newArr1[i])
    }
}

5、去重办法五(排序后相邻去重法)

// 给传入数组排序,排序后雷同值相邻,而后遍历时新数组只退出不与前一值反复的值。function unique3(arr) {arr.sort();
    var newArr = [arr[0]];
    for(var i = 1, len = arr.length; i < len; i++) {if(arr[i] !== newArr[newArr.length - 1]) {newArr.push(arr[i]);
        }
    }
    return newArr;
}
var duplicate4 = unique3(newArr1)

三、数组排序

1、sort 排序

function arrSort(arr) {return arr.sort(function(a, b) {return a - b})
}
var sort = arrSort(initarr)

2、冒泡排序

function bubbleSort(arr){
    let arrLen = arr.length-1
    for(let i = 0;i < arrLen;i++){for(let j = 0;j<arrLen-i;j++){if( arr[j]>arr[j+1] ){let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp
            }
        }
    }
    return arr
}
bubbleSort(initarr)

3、插入排序

function insertSort(arr) {
    // 假如第一个元素曾经排好序
    for (let i = 1; i < arr.length; i++) {if (arr[i] < arr[i - 1]) {
            // 取出无序序列中须要插入的第 i 个元素
            var temp = arr[i];
            // 定义有序中的最初一个地位
            var j = i - 1;
            arr[i] = arr[j];
            // 依据序列最初一位,一直循环比拟,找到插入的地位
            while(j >= 0 && temp < arr[j]){arr[ j+1] = arr[j];
                j--;
            };
            // 插入
            arr[j+1] = temp;
        }
    }
}
var sort2 = insertSort(initarr)

4、希尔排序

function shellSort(arr) {
    var len = arr.length;
    // 定义距离区间
    var fraction = Math.floor(len / 2);
    // fraction = Math.floor(fraction / 2) => 循环中一直切割区间
    for (fraction; fraction > 0; fraction = Math.floor(fraction / 2)) {
        // 以距离值开始遍历
        for (var i = fraction; i < len; i++) {
            // 如果后面一个大于前面一个
            for (var j = i - fraction; j >= 0 && arr[j] > arr[fraction + j]; j -= fraction) {var temp = arr[j];
                arr[j] = arr[fraction + j]; // 后移
                arr[fraction + j] = temp; // 填补
            }
        }
    }
}
var sort3 = shellSort(initarr)

四、交加、并集、差集

1、ES7 的形式

// 并集
  let union = a.concat(b.filter(v => !a.includes(v))) // [1,2,3,4,5]
  // 交加
  let intersection = a.filter(v => b.includes(v)) // [2]
  // 差集
  let difference = a.concat(b).filter(v => a.includes(v) && !b.includes(v)) // [1,3]

2、ES6

let aSet = new Set(a)
    let bSet = new Set(b)
    
    // 并集
    let union = Array.from(new Set(a.concat(b))) // [1,2,3,4,5]
    
    // 交加
    let intersection = Array.from(new Set(a.filter(v => bSet.has(v))))
    
    // 差集
    let differenceNew = Array.from(new Set(a.concat(b).filter(v => aSet.has(v) && !bSet.has(v))))

3、ES5

// 并集
    var union = a.concat(b.filter(function(v) {return a.indexOf(v) === -1})) // [1,2,3,4,5]
 
    // 交加
    var intersection = a.filter(function(v){return b.indexOf(v) > -1 }) // [2]
 
    // 差集
    var difference = a.filter(function(v){return b.indexOf(v) === -1 })// [1,3]

思考有 NaN

var a = [1, 2, 3, NaN];
    var b = [2, 4, 5];
 
    var aHasNaN = a.some(function (v) {return isNaN(v)
    })
    var bHasNaN = b.some(function (v) {return isNaN(v)
    })
 
    // 并集
    var union = a.concat(b.filter(function (v) {return a.indexOf(v) === -1 && !isNaN(v)
    })).concat(!aHasNaN & bHasNaN ? [NaN] : []) // [1,2,3,4,5,NaN]
 
    // 交加
    var intersection = a.filter(function (v) {return b.indexOf(v) > -1
    }).concat(aHasNaN & bHasNaN ? [NaN] : []) // [2]
 
    // 差集
    var difference = a.filter(function (v) {return b.indexOf(v) === -1 && !isNaN(v)
    }).concat(aHasNaN && !bHasNaN ? [NaN] : [])//1,3,NaN

五、二分查找
应用二分查找前提是有序数组

function halfSearch(arr,aim){
    let min = 0,
        max = arr.length-1;

    while(min<=max){let half = parseInt((min + max)/2)
        if(aim == arr[half] ){return half}else if(arr[half] > aim ){max = half - 1}else if(arr[half] < aim ){min = half + 1}
    }
    return -1
}

六、峰值地位查找

1. 当查找的峰值为最大值的状况:

// 二分查找法
var findPeakElement = function(nums) {
    let low = 0;
    let high = nums.length - 1;
    let mid;
    while(low < high) {mid = Math.floor((low+high)/2);
        if (nums[mid] > nums[mid+1]) {high = mid;} else {low = mid + 1;}
    }
    return high;
}

// 或者间接调用 js 接口:let peakVal = arr => {return arr.indexOf(Math.max(...arr))
}

2. 当峰值为该值大于左右相邻元素的值得状况:

let peakVal1 = arr => {
    let len = arr.length-1,
        peakValArr = [];
    for(let i = 0; i < len;i++){if( arr[i]>arr[i-1] && arr[i]>arr[i+1] ){peakValArr.push(i)
        }else if(arr[0]>arr[1]){peakValArr = [0]
        }else{peakValArr = [len]
        }
    }
    return peakValArr.join()}

正文完
 0