C++程序 查找正方形矩阵中的最大值和最小值
给定一阶为n的正方形矩阵,在该矩阵中查找最大值和最小值。
示例:
输入: arr[][] = {5, 4, 9,
2, 0, 6,
3, 1, 8};
输出: 最大值 = 9,最小值 = 0
输入: arr[][] = {-5, 3,
2, 4};
输出: 最大值 = 4,最小值 = -5
朴素法:
我们使用线性搜索分别查找矩阵的最大值和最小值。查找最小值需要n 2 次比较,查找最大值需要n 2 次比较。总比较次数等于2n 2 。
// 查找矩阵中的最大值和最小值。
#include<bits/stdc++.h>
using namespace std;
void maxMin(int arr[3][3], int n)
{
int min = INT_MAX;
int max = INT_MIN;
// 查找给定数组中的最大元素
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(max < arr[i][j]) max = arr[i][j];
}
}
// 查找给定数组中的最小元素
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(min > arr[i][j]) min = arr[i][j];
}
}
cout << "最大值 = " << max << ",最小值 = " << min;
}
int main(){
int arr[3][3] = {{5, 9, 11} , {25, 0, 14} , {21, 6, 4}};
maxMin(arr, 3);
return 0;
}
// 该代码由KIRTI AGARWAL(KIRTIAGARWAL23121999)贡献。```
输出
最大值 = 25,最小值 = 0
成对比较(高效方法):
从矩阵中选择两个元素,一个是矩阵行的开头,另一个是同一行的末尾,比较它们,然后将它们中较小的比较矩阵中的最小值,大的比较矩阵中的最大值。我们可以看到对于两个元素,我们需要3次比较,因此对于遍历整个矩阵,我们需要总共3/2 n 2 次比较。
注意:
这是数组的最大最小值的第3种方法的扩展形式。
// 查找矩阵中的最大值和最小值。
#include<bits/stdc++.h>
using namespace std;
#define MAX 100
void maxMin(int arr[][MAX], int n)
{
int min = INT_MAX;
int max = INT_MIN;
// 逐行遍历数组
for (int i = 0; i <n; i++)
{
for (int j = 0; j <= n/2; j++)
{
// 比较当前行开头和结尾的元素
if (arr[i][j] > arr[i][n-j-1])
{
if (min > arr[i][n-j-1])
min = arr[i][n-j-1];
if (max< arr[i][j])
max = arr[i][j];
}
else
{
if (min > arr[i][j])
min = arr[i][j];
if (max< arr[i][n-j-1])
max = arr[i][n-j-1];
}
}
}
cout << "最大值 = " << max;
<< ",最小值 = " << min;
}
int main()
{
int arr[MAX][MAX] = {5, 9, 11,
25, 0, 14,
21, 6, 4};
maxMin(arr, 3);
return 0;
}
输出:
最大值 = 25,最小值 = 0
时间复杂度:O(n^2)
辅助空间:O(1) 因为没有额外的空间被占用。