【每日一题】- 2019-08-27 - 寻找数组中的最大值和最小值

[azl397985856]

【每日一题】- 2019-08-27 - 寻找数组中的最大值和最小值

[SChen1024]

无序数组中求最大值和最小值的最少比较次数

原理介绍

求一个无序数组中的最大值和最小值是一个很常见的情况, 一般来说, 最大值和最小值不是同一个元素, 我们可以通过下面几种方法来求:

1. 排序算法:将数组排序后, 第一个元素是最小值,最后一个元素是最大值,以快排平均复杂度为例,时间复杂度 $O(NlogN)$,空间复杂度: $O(logN)$,比较次数: $NlogN$ ;
2. 两个元素记录最大值和最小值,判断每个值是否大于最大值或者最小值, 比较次数: $2*N$';
3. 使用两个值记录最大值和最小值, 每次取出两个值,先进行比较,小的与最小值比较,大的与最大值比较 , 比较次数: $1.5*N$
4. 将相邻的数进行比较,大的放在偶数位置,小的放在奇数位置, 最后奇数位置比较和偶数位置对应比较,得到最大值和最小值,比较次数: $1.5*N$ ;
5. 分治法, topK 问题的简化版本分成两部分,找到前半部分的 Min Max, 最后比较结果可得到最后的值

方法3 和方法4的 过程很接近, 方法3 更为容易实现, 具体实现可见后续

算法实现

方法1 快排

// 找到数组元素的最大值和最小值 
vector<int> findMinMax(vector<int> arr)
{
    sort(arr.begin(),arr.end());
    return {arr[0],arr.back()};
}

方法 2

// 找到数组元素的最大值和最小值 
vector<int> findMinMax(vector<int> arr)
{
    int min_ = INT_MAX,max_ = INT_MIN;
    for(int i=0;i<arr.size();++i)
    {
        if(arr[i] > max_)
            max_ = arr[i];
        if(arr[i] < min_)
            min_ = arr[i];
    }
    return {min_,max_};
}

方法 3

使用两个值记录最大值和最小值, 每次取出两个值,先进行比较,小的与最小值比较,大的与最大值比较 , 比较次数: $1.5*N$

// 找到数组元素的最大值和最小值 
vector<int> findMinMax(vector<int> arr) {
    int min_ = INT_MAX,max_ = INT_MIN;
    // 处理前面偶数个元素
    for(int i=0;i<arr.size()/2;++i) {
        // 得到两个元素的最大值和最小值
        int tmp_min,tmp_max;
        if(arr[i] < arr[i+1]) {
            tmp_min = arr[i];
            tmp_max = arr[i+1];
        } else {
            tmp_min = arr[i+1];
            tmp_max = arr[i];
        }
        // 比较,更新最大值和最小值
        if(tmp_max > max_)  max_ = tmp_max;
        if(tmp_min < min_)  min_ = tmp_min;
    }

    // 处理数组个数为奇数的情况 // 处理最后一个元素
    if(arr.size()%2) {
        int tmp = arr.back();
        if(tmp > max_)  max_ = tmp;
        if(tmp < min_)  min_ = tmp;
    }

    return {min_,max_};
}

方法 4

比较前面偶数个元素,小的放在奇数位置,大的放在偶数位置, 比较次数: $1.5*N$

// 找到数组元素的最大值和最小值 
vector<int> findMinMax(vector<int> arr) {
    int min_ = INT_MAX,max_ = INT_MIN;
    // 调整位置, 小的位于奇数,大的位置偶数
    for(int i=0;i<arr.size()/2;i++) {
        if(arr[i] > arr[i+1])   swap(arr[i],arr[i+1]);
    }
    // 更新最大值和最小值
    for(int i=0;i<arr.size()/2;i++) {
        if(arr[i] < min_)   min_ = arr[i];
        if(arr[i+1] > max_) max_ = arr[i+1];
    }

    // 处理数组个数为奇数的情况 // 处理最后一个元素
    if(arr.size()%2) {
        int tmp = arr.back();
        if(tmp > max_)  max_ = tmp;
        if(tmp < min_)  min_ = tmp;
    }

    return {min_,max_};
}

方法5

在N个数中求最小值Min和Max, 分成两个部分,依次取Min和Max,
略

参考链接

1. 关于在一个无序数组中的数求最大值和最小值的最小比较次数
   
2. 无序数组同时查找最大和最小的元素
3. 面试题-算法：乱序数组中找最大值和最小值
4. 【编程之美】读书笔记：寻找数组中的最大值和最小值

[mugenmagic]

function quickSort(array, lowIndex, highIndex) {
    if (lowIndex < highIndex) {
        const pivotIndex = partition(array, lowIndex, highIndex)

        quickSort(array, lowIndex, pivotIndex - 1)
        quickSort(array, pivotIndex + 1, highIndex)
    }
}

function partition(array, lowIndex, highIndex) {
    const pivotValue = array[highIndex];
    let lowerIndex = lowIndex - 1;

    for (let i = lowIndex; i <= highIndex - 1; i++) {
        if (array[i] < pivotValue) {
            lowerIndex++;

            const temp = array[lowerIndex];
            array[lowerIndex] = array[i];
            array[i] = temp;
        }
    }

    const temp = array[lowerIndex + 1];
    array[lowerIndex + 1] = array[highIndex];
    array[highIndex] = temp;

    return lowerIndex + 1;
}

let i = 0;
const randArray = [];
while(i < 20) {
    randArray.push(Math.floor(Math.random() * Math.floor(100)));
    i++;
}

quickSort(randArray, 0, randArray.length - 1)
console.log('Array:', randArray);
console.log('Smallest value:', randArray[0]);
console.log('Biggest value:', randArray[randArray.length - 1]);

[xiongcaihu]

/**
 * 无序数组的样子就跟股票的走势一样，有一段上升，有一段下降，又有一段持平
 * 那么我们每次比较时，只要在那些转折点进行比较即可
 * 这样，如果这个无序数组这种上升或者下降趋势越长，比较次数减少的越多
 *
 * @param {*} nums
 * @returns
 */
function findMaxAndMin(nums) {
	var max = nums[0],
		min = nums[0];
	var count = 0;
	for (var i = 1; i < nums.length; i++) {
		if (nums[i] > nums[i - 1]) {
			// 上升趋势
			var j = i;
			while (nums[j] <= nums[j + 1]) {
				j++;
			}
			max = Math.max(max, nums[j]);
			i = j;
		} else {
			// 下降趋势
			var j = i;
			while (nums[j] >= nums[j + 1]) {
				j++;
			}
			min = Math.min(min, nums[j]);
			i = j;
		}
		count++;
	}

	return {
		max,
		min,
		count
	};
}

var timestart = new Date().getTime();
console.log(findMaxAndMin([1, 2, 3, 3, 4, 5, 5, 7]));
console.log(findMaxAndMin([7, 6, 5]));
console.log(findMaxAndMin([1, 2, 3, 2, 0, -100, 1000]));
console.log(findMaxAndMin([1, 2, 3, 3, 3, 2, 1]));
console.log(findMaxAndMin([1,1,1,1,1,1,1,-100,-101,-1000,2,3,4,5,6,7,7,7,7,-10000]));
console.log(findMaxAndMin([1000,1,2,1,2,1,0,11000]));
console.log("use time = ", new Date().getTime() - timestart);

[azl397985856]

/**
 * 无序数组的样子就跟股票的走势一样，有一段上升，有一段下降，又有一段持平
 * 那么我们每次比较时，只要在那些转折点进行比较即可
 * 这样，如果这个无序数组这种上升或者下降趋势越长，比较次数减少的越多
 *
 * @param {*} nums
 * @returns
 */
function findMaxAndMin(nums) {
	var max = nums[0],
		min = nums[0];
	var count = 0;
	for (var i = 1; i < nums.length; i++) {
		if (nums[i] > nums[i - 1]) {
			// 上升趋势
			var j = i;
			while (nums[j] <= nums[j + 1]) {
				j++;
			}
			max = Math.max(max, nums[j]);
			i = j;
		} else {
			// 下降趋势
			var j = i;
			while (nums[j] >= nums[j + 1]) {
				j++;
			}
			min = Math.min(min, nums[j]);
			i = j;
		}
		count++;
	}

	return {
		max,
		min,
		count
	};
}

var timestart = new Date().getTime();
console.log(findMaxAndMin([1, 2, 3, 3, 4, 5, 5, 7]));
console.log(findMaxAndMin([7, 6, 5]));
console.log(findMaxAndMin([1, 2, 3, 2, 0, -100, 1000]));
console.log(findMaxAndMin([1, 2, 3, 3, 3, 2, 1]));
console.log(findMaxAndMin([1,1,1,1,1,1,1,-100,-101,-1000,2,3,4,5,6,7,7,7,7,-10000]));
console.log(findMaxAndMin([1000,1,2,1,2,1,0,11000]));
console.log("use time = ", new Date().getTime() - timestart);

是的，这种做法最坏的情况还是2N次比较.

你这里的count不是比较次数

[xiongcaihu]

是的，这种做法最坏的情况还是2N次比较

没有吧，最坏N次比较

[CC-cat]

var arr = [7, 2, 0, -3, 5, 9];
var max = Math.max.apply(null, arr);
var min = Math.min.apply(null, arr);
console.log(max, min);

输出：
9 -3

[azl397985856]

var arr = [7, 2, 0, -3, 5, 9];

var max = Math.max.apply(null, arr);
var min = Math.min.apply(null, arr);
console.log(max, min);
输出：
9 -3

兄弟 你没有理解题

[azl397985856]

实际上只需要1.5N次比较，N是数组的长度

[Veveue]

@azl397985856 先排序 然后直接取首尾行不行

[azl397985856]

@azl397985856 先排序 然后直接取首尾行不行

你算一下需要比较多少次

[azl397985856]

@SChen1024 方便领取一下么

[SChen1024]

不知道怎么领取, 找了下 , 不知道怎么操作或者加入, 就直接回复了, 直接诶回复领取吗? 之后需要做什么呢?

[azl397985856]

@SChen1024 done 已经指派给你了 具体的认领步骤在这里： https://github.com/azl397985856/leetcode/tree/master/daily