数据结构

数组

求数组最大最小值

  • 通过prototype属性扩展min()函数和max()函数

1.for+if

通过prototype属性扩展min()函数和max()函数

算法1的思路是在自定义min()和max()函数中，通过循环由第一个值依次与后面的值作比较，动态更新最大值和最小值，从而找到结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 最小值
Array.prototype.min = function () {
    let min = this[0];
    let len = this.length;
    for (let i = 1; i < len; i++) {
        if (this[i] < min) min = this[i]
    }
    return min
}
// 最大值
Array.prototype.max = function () {
    let max = this[0];
    let len = this.length;
    for (let i = 1; i < len; i++) {
        if (this[i] > max) max = this[i]
    }
    return max
}
// 结果
console.log(arr.min()); // 1
console.log(arr.max()); // 9

2.借助Math对象的min()函数和max()函数

算法2的主要思路是通过apply()函数改变函数的执行体，将数组作为参数传递给apply()函数。这样数组就可以直接调用Math对象的min()函数和max()函数来获取返回值。

1
2
3
4
5
6
7
8
9
10
11
Array.min = function(array) {
    return Math.min.apply(Math, array)
}
// 最大值
Array.max = function (array) {
    return Math.max.apply(Math, array)
}
// 结果
console.log(Array.min(arr)); // 1
console.log(Array.max(arr)); // 9

1
2
let values = [1, 2, 3, 4, 5, 6, 7, 8]; 
let max = Math.max(...val);

3.算法2的优化

实现数组排序

自己第一次想的

  • 取数组最小值和最大值，并记录索引
  • 根据索引去过滤掉原数组中的这两个值，然后将这两个值从中间插入到新数组
  • 递归上述操作
    • 注意点，不同的数组长度做一下边界处理
    • 最后数组长度为1时，插入的时候，注意下边界处理
  • 核心：递归在最小值最大值组成的数组的中间，依次插入第二小值和第二大值，起始一定是最小，末尾一定是最大

自己实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
const arr = [7, 2, 3, 2, 6, 9 ,0 ,11,11]

let getMin = function getMin(arr) {
    let minValue = 0,
    minIndex = 0
    arr.forEach((item, index) => {
        if (index === 0) {
            minValue = item
            return
        }
        if (item <= minValue) {
            minValue = item
            minIndex = index
        }
    })
    // console.log('最小值', minValue, minIndex)
    return { minValue, minIndex }
}

let getMax = function getMax(arr) {
    let maxValue = 0,
    maxIndex = 0
    arr.forEach((item, index) => {
        if (index === 0) {
            maxValue = item
            return
        }
        if (item > maxValue) {
            maxValue = item
            maxIndex = index
        }
    })
    console.log('最大值', maxValue, maxIndex)

    return { maxValue, maxIndex }
}

let filterMinAndMax = function filterMinAndMax(minIndex, maxIndex, arr) {
    let newArr = []
    arr.forEach((item, index) => {
        if (index === minIndex || index === maxIndex) return
        newArr.push(item)
    })
    return newArr
}

let sortArray = [], newArr = []
let main = function main(arr) {
    if(arr.length === 0 ) return
    if(arr.length === 1) {
        let onlyValue = arr[0]
        const insertIndex = sortArray.length / 2
        if(onlyValue > sortArray[insertIndex]) {
            sortArray.splice(insertIndex + 1, 0, onlyValue)
        } else {
            sortArray.splice(insertIndex, 0, onlyValue)
        }

        console.log('res', sortArray)
        return
    }

    if(arr.length > 1) {
        let { minValue, minIndex } = getMin(arr)
        let { maxValue, maxIndex } = getMax(arr)
        console.log( minValue, maxValue)
        if(sortArray.length % 2 === 0){
            const insertIndex = sortArray.length / 2
            sortArray.splice(insertIndex, 0, minValue, maxValue)
            console.log('sortArray', sortArray)
        }
    
    
        newArr = filterMinAndMax(minIndex, maxIndex, arr)
        console.log('newArr', newArr)
    }

    main(newArr)
}
// getMax(arr)
main(arr)

更加js的写法

1