求數組中的最大值和最小值

2019-11-08 00:19:16

字體：大中小

來源：轉載

供稿：網友

方法1：暴力方法遍歷一遍數組，比較2*N次求出最大值和最小值

方法2：改進方法（破壞了原數組）遍歷一遍數組使得下標為偶數的元素較下標為奇數的元素大,再分別求出最大值和最小值比較次數為3*N/2次

方法3：改進方法（不破壞原數組）遍歷一遍數組將相鄰元素中較大值和nMax比較,將較小值和nMin比較 比較次數為3*N/2次

方法4：改進方法 分治思想，先分別求出前半部分和后半部分數組的最大值和最小值，然后兩部分中的最大值和最小值分別比較求出整個數組的最大值和最小值比較次數為3*N/2-2次

代碼如下：

[cpp] view plain copy// 求數組中的最大值最小值.cpp : 定義控制臺應用程序的入口點。 #include "stdafx.h" #include <iostream> using namespace std; //方法一：暴力方法遍歷一遍數組，比較2*N次求出最大值和最小值 void FindMaxAndMinMethod1(int *pArr, int nLength, int &nMax, int &nMin) { if (pArr == NULL || nLength <= 0) { cout << "輸入有誤！" << endl; return; } nMax = pArr[0]; nMin = pArr[0]; for (int i=1; i<nLength; i++) { if (nMin > pArr[i]) { nMin = pArr[i]; } if (nMax < pArr[i]) { nMax = pArr[i]; } } } //方法二：改進方法（破壞了原數組） //遍歷一遍數組使得下標為偶數的元素較下標為奇數的元素大,再分別求出最大值和最小值 //比較次數為3*N/2次 void FindMaxAndMinMethod2(int *pArr, int nLength, int &nMax, int &nMin) { if (pArr != NULL && nLength > 0) { if (nLength == 1)//數組只有一個元素 { nMax = pArr[0]; nMin = pArr[0]; return; } if (nLength == 2)//數組只有兩個元素 { if (pArr[0] > pArr[1]) { nMax = pArr[0]; nMin = pArr[1]; } else { nMax = pArr[1]; nMin = pArr[0]; } return; } //遍歷一遍數組使得下標為偶數的元素較下標為奇數的元素大 for (int i=0; i<nLength; i+=2) { if (i+1 < nLength && pArr[i] < pArr[i+1]) { int nTemp = pArr[i]; pArr[i] = pArr[i+1]; pArr[i+1] = nTemp; } } //求最大值 nMax = pArr[0]; for (int j=2; j<nLength; j+=2) { if (nMax < pArr[j]) { nMax = pArr[j]; } } //求最小值 nMin = pArr[1]; for (int t=3; t<nLength; t+=2) { if (nMin > pArr[t]) { nMin = pArr[t]; } } } } //方法三：改進方法（不破壞原數組） //遍歷一遍數組將相鄰元素中較大值和nMax比較,將較小值和nMin比較 //比較次數為3*N/2次 void FindMaxAndMinMethod3(int *pArr, int nLength, int &nMax, int &nMin) { if (pArr != NULL && nLength > 0) { if (nLength == 1)//數組只有一個元素 { nMax = pArr[0]; nMin = pArr[0]; return; } if (nLength == 2)//數組只有兩個元素 { if (pArr[0] > pArr[1]) { nMax = pArr[0]; nMin = pArr[1]; } else { nMax = pArr[1]; nMin = pArr[0]; } return; } //初始賦值 if (pArr[0] > pArr[1]) { nMax = pArr[0]; nMin = pArr[1]; } else { nMax = pArr[1]; nMin = pArr[0]; } for (int i=2; i<nLength; i+=2) { if (i+1 < nLength && pArr[i] < pArr[i+1]) { if (nMax < pArr[i+1])//將較大值和nMax比較 { nMax = pArr[i+1]; } if (nMin > pArr[i])//將較小值和nMin比較 { nMin = pArr[i]; } } else if (i+1 < nLength && pArr[i] > pArr[i+1]) { if (nMax < pArr[i])//將較大值和nMax比較 { nMax = pArr[i]; } if (nMin > pArr[i+1])//將較小值和nMin比較 { nMin = pArr[i+1]; } } else//最后剩下一個元素 { if (nMax < pArr[i]) { nMax = pArr[i]; } if (nMin > pArr[i]) { nMin = pArr[i]; } } } } } //方法四：改進方法 //分治思想，先分別求出前半部分和后半部分數組的最大值和最小值， //然后兩部分中的最大值和最小值分別比較求出整個數組的最大值和最小值 //比較次數為3*N/2-2次 void FindMaxAndMinMethod4(int *pArr, int nStart, int nEnd, int &nMax, int &nMin) { if (nEnd - nStart <= 1) { if (pArr[nStart] > pArr[nEnd]) { nMax = pArr[nStart]; nMin = pArr[nEnd]; } else { nMax = pArr[nEnd]; nMin = pArr[nStart]; } return; } int nLeftMax = 0; int nLeftMin = 0; int nRightMax = 0; int nRightMin = 0; FindMaxAndMinMethod4(pArr, nStart, nStart+(nEnd-nStart)/2, nLeftMax, nLeftMin); FindMaxAndMinMethod4(pArr, nStart+(nEnd-nStart)/2+1, nEnd, nRightMax, nRightMin); nMax = nLeftMax > nRightMax ? nLeftMax : nRightMax; nMin = nLeftMin < nRightMin ? nLeftMin : nRightMin; } int _tmain(int argc, _TCHAR* argv[]) { //int nArr[1] = {-4}; //int nArr[2] = {-4,-1}; //int nArr[3] = {-4,-1,0}; int nArr[5] = {-4,-1,0, 8,9}; int max = 0; int min = 0; FindMaxAndMinMethod1(nArr, 5, max, min); cout << "最大值為：" << max << " 最小值為：" << min << endl; max = 0; min = 0; FindMaxAndMinMethod2(nArr, 5, max, min); cout << "最大值為：" << max << " 最小值為：" << min << endl; max = 0; min = 0; FindMaxAndMinMethod3(nArr, 5, max, min); cout << "最大值為：" << max << " 最小值為：" << min << endl; max = 0; min = 0; FindMaxAndMinMethod4(nArr, 0, 4, max, min); cout << "最大值為：" << max << " 最小值為：" << min << endl; system("pause"); return 0; }

運行結果：