Comments (13)
无序数组中求最大值和最小值的最少比较次数
原理介绍
求一个无序数组中的最大值和最小值是一个很常见的情况, 一般来说, 最大值和最小值不是同一个元素, 我们可以通过下面几种方法来求:
- 排序算法:将数组排序后, 第一个元素是最小值,最后一个元素是最大值,以快排平均复杂度为例,时间复杂度
$O(NlogN)$ ,空间复杂度:$O(logN)$ ,比较次数:$NlogN$ ; - 两个元素记录最大值和最小值,判断每个值是否大于最大值或者最小值, 比较次数:
$2*N$ '; - 使用两个值记录最大值和最小值, 每次取出两个值,先进行比较,小的与最小值比较,大的与最大值比较 , 比较次数:
$1.5*N$ - 将相邻的数进行比较,大的放在偶数位置,小的放在奇数位置, 最后奇数位置比较和偶数位置对应比较,得到最大值和最小值,比较次数:
$1.5*N$ ; - 分治法, 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
使用两个值记录最大值和最小值, 每次取出两个值,先进行比较,小的与最小值比较,大的与最大值比较 , 比较次数:
// 找到数组元素的最大值和最小值
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
比较前面偶数个元素,小的放在奇数位置,大的放在偶数位置, 比较次数:
// 找到数组元素的最大值和最小值
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,
略
参考链接
from leetcode.
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]);
from leetcode.
/**
* 无序数组的样子就跟股票的走势一样,有一段上升,有一段下降,又有一段持平
* 那么我们每次比较时,只要在那些转折点进行比较即可
* 这样,如果这个无序数组这种上升或者下降趋势越长,比较次数减少的越多
*
* @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);
from leetcode.
/** * 无序数组的样子就跟股票的走势一样,有一段上升,有一段下降,又有一段持平 * 那么我们每次比较时,只要在那些转折点进行比较即可 * 这样,如果这个无序数组这种上升或者下降趋势越长,比较次数减少的越多 * * @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不是比较次数
from leetcode.
是的,这种做法最坏的情况还是2N次比较
没有吧,最坏N次比较
from leetcode.
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
from leetcode.
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
兄弟 你没有理解题
from leetcode.
实际上只需要1.5N次比较,N是数组的长度
from leetcode.
@azl397985856 先排序 然后直接取首尾行不行
from leetcode.
@azl397985856 先排序 然后直接取首尾行不行
你算一下需要比较多少次
from leetcode.
@SChen1024 方便领取一下么
from leetcode.
不知道怎么领取, 找了下 , 不知道怎么操作或者加入, 就直接回复了, 直接诶回复领取吗? 之后需要做什么呢?
from leetcode.
@SChen1024 done 已经指派给你了 具体的认领步骤在这里: https://github.com/azl397985856/leetcode/tree/master/daily
from leetcode.
Related Issues (20)
- 树专题中双色标记法后序和前序写反了 HOT 2
- leetcode/thinkings/tree.md 出错 HOT 1
- some error
- 二分查找专题,寻找最左/右插入位置算法模板错误问题 HOT 9
- possible code error in thinkings/heap.md HOT 1
- link error HOT 4
- link is not correct
- [695.最大岛屿面积,360,面试原题]【每日一题】 HOT 3
- 【专题】 反向思考 HOT 3
- 【专题】 考虑每一项对结果到的贡献
- 【专题】递推方程时间复杂度优化
- 已发布文章的代码错误 HOT 7
- Remove duplicate CPP solution and add Python solution for problem 100.same-tree
- Add OSSF Scorecard security workflow
- 题目的排版可否改一改
- 关于二分法中查找中间点索引的算式 HOT 6
- leetcode-thinkings-tree.md BFS 模版调整 HOT 3
- anki-card 中只有10道题吗?截止到2023.11 HOT 1
- 【每日一题】- 2020-xx-xx - xxx
- 大佬,考虑出一个最短路径的专题吗 HOT 8
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from leetcode.