编写一个C函数来返回数组中的最小值和最大值。你的程序应该进行最少的比较。
首先,我们如何从C函数返回多个值?我们可以使用结构或指针来实现。 我们创建了一个名为pair(包含min和max)的结构来返回多个值。
C
struct pair { int min; int max; }; |
函数声明变成:struct pair getMinMax(int arr[],int n),其中arr[]是大小为n的数组,其最小值和最大值都是必需的。
方法1(简单线性搜索) 将最小值和最大值分别初始化为前两个元素的最小值和最大值。从第三个开始,将每个元素与最大值和最小值进行比较,并相应地更改最大值和最小值(即,如果元素小于最小值,则更改最小值,否则如果元素大于最大值,则更改最大值,否则忽略该元素)
C++
// C++ program of above implementation #include<iostream> using namespace std; // Pair struct is used to return // two values from getMinMax() struct Pair { int min; int max; }; Pair getMinMax( int arr[], int n) { struct Pair minmax; int i; // If there is only one element // then return it as min and max both if (n == 1) { minmax.max = arr[0]; minmax.min = arr[0]; return minmax; } // If there are more than one elements, // then initialize min and max if (arr[0] > arr[1]) { minmax.max = arr[0]; minmax.min = arr[1]; } else { minmax.max = arr[1]; minmax.min = arr[0]; } for (i = 2; i < n; i++) { if (arr[i] > minmax.max) minmax.max = arr[i]; else if (arr[i] < minmax.min) minmax.min = arr[i]; } return minmax; } // Driver code int main() { int arr[] = { 1000, 11, 445, 1, 330, 3000 }; int arr_size = 6; struct Pair minmax = getMinMax(arr, arr_size); cout << "Minimum element is " << minmax.min << endl; cout << "Maximum element is " << minmax.max; return 0; } // This code is contributed by nik_3112 |
C
/* structure is used to return two values from minMax() */ #include<stdio.h> struct pair { int min; int max; }; struct pair getMinMax( int arr[], int n) { struct pair minmax; int i; /*If there is only one element then return it as min and max both*/ if (n == 1) { minmax.max = arr[0]; minmax.min = arr[0]; return minmax; } /* If there are more than one elements, then initialize min and max*/ if (arr[0] > arr[1]) { minmax.max = arr[0]; minmax.min = arr[1]; } else { minmax.max = arr[1]; minmax.min = arr[0]; } for (i = 2; i<n; i++) { if (arr[i] > minmax.max) minmax.max = arr[i]; else if (arr[i] < minmax.min) minmax.min = arr[i]; } return minmax; } /* Driver program to test above function */ int main() { int arr[] = {1000, 11, 445, 1, 330, 3000}; int arr_size = 6; struct pair minmax = getMinMax (arr, arr_size); printf ( "nMinimum element is %d" , minmax.min); printf ( "nMaximum element is %d" , minmax.max); getchar (); } |
JAVA
// Java program of above implementation public class GFG { /* Class Pair is used to return two values from getMinMax() */ static class Pair { int min; int max; } static Pair getMinMax( int arr[], int n) { Pair minmax = new Pair(); int i; /*If there is only one element then return it as min and max both*/ if (n == 1 ) { minmax.max = arr[ 0 ]; minmax.min = arr[ 0 ]; return minmax; } /* If there are more than one elements, then initialize min and max*/ if (arr[ 0 ] > arr[ 1 ]) { minmax.max = arr[ 0 ]; minmax.min = arr[ 1 ]; } else { minmax.max = arr[ 1 ]; minmax.min = arr[ 0 ]; } for (i = 2 ; i < n; i++) { if (arr[i] > minmax.max) { minmax.max = arr[i]; } else if (arr[i] < minmax.min) { minmax.min = arr[i]; } } return minmax; } /* Driver program to test above function */ public static void main(String args[]) { int arr[] = { 1000 , 11 , 445 , 1 , 330 , 3000 }; int arr_size = 6 ; Pair minmax = getMinMax(arr, arr_size); System.out.printf( "Minimum element is %d" , minmax.min); System.out.printf( "Maximum element is %d" , minmax.max); } } |
蟒蛇3
# Python program of above implementation # structure is used to return two values from minMax() class pair: def __init__( self ): self . min = 0 self . max = 0 def getMinMax(arr: list , n: int ) - > pair: minmax = pair() # If there is only one element then return it as min and max both if n = = 1 : minmax. max = arr[ 0 ] minmax. min = arr[ 0 ] return minmax # If there are more than one elements, then initialize min # and max if arr[ 0 ] > arr[ 1 ]: minmax. max = arr[ 0 ] minmax. min = arr[ 1 ] else : minmax. max = arr[ 1 ] minmax. min = arr[ 0 ] for i in range ( 2 , n): if arr[i] > minmax. max : minmax. max = arr[i] elif arr[i] < minmax. min : minmax. min = arr[i] return minmax # Driver Code if __name__ = = "__main__" : arr = [ 1000 , 11 , 445 , 1 , 330 , 3000 ] arr_size = 6 minmax = getMinMax(arr, arr_size) print ( "Minimum element is" , minmax. min ) print ( "Maximum element is" , minmax. max ) # This code is contributed by # sanjeev2552 |
C#
// C# program of above implementation using System; class GFG { /* Class Pair is used to return two values from getMinMax() */ class Pair { public int min; public int max; } static Pair getMinMax( int []arr, int n) { Pair minmax = new Pair(); int i; /* If there is only one element then return it as min and max both*/ if (n == 1) { minmax.max = arr[0]; minmax.min = arr[0]; return minmax; } /* If there are more than one elements, then initialize min and max*/ if (arr[0] > arr[1]) { minmax.max = arr[0]; minmax.min = arr[1]; } else { minmax.max = arr[1]; minmax.min = arr[0]; } for (i = 2; i < n; i++) { if (arr[i] > minmax.max) { minmax.max = arr[i]; } else if (arr[i] < minmax.min) { minmax.min = arr[i]; } } return minmax; } // Driver Code public static void Main(String []args) { int []arr = {1000, 11, 445, 1, 330, 3000}; int arr_size = 6; Pair minmax = getMinMax(arr, arr_size); Console.Write( "Minimum element is {0}" , minmax.min); Console.Write( "Maximum element is {0}" , minmax.max); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program of above implementation /* Class Pair is used to return two values from getMinMax() */ function getMinMax(arr, n) { minmax = new Array(); var i; var min; var max; /*If there is only one element then return it as min and max both*/ if (n == 1) { minmax.max = arr[0]; minmax.min = arr[0]; return minmax; } /* If there are more than one elements, then initialize min and max*/ if (arr[0] > arr[1]) { minmax.max = arr[0]; minmax.min = arr[1]; } else { minmax.max = arr[1]; minmax.min = arr[0]; } for (i = 2; i < n; i++) { if (arr[i] > minmax.max) { minmax.max = arr[i]; } else if (arr[i] < minmax.min) { minmax.min = arr[i]; } } return minmax; } /* Driver program to test above function */ var arr = [1000, 11, 445, 1, 330, 3000]; var arr_size = 6; minmax = getMinMax(arr, arr_size); document.write( "Minimum element is " ,minmax.min + "<br>" ); document.write( "Maximum element is " , minmax.max); // This code is contributed by shivanisinghss2110 </script> |
输出:
Minimum element is 1Maximum element is 3000
时间复杂性: O(n)
在这种方法中,最坏情况下的比较总数为1+2(n-2),最好情况下的比较总数为1+n–2。 在上述实现中,最坏的情况发生在元素按降序排序时,最好的情况发生在元素按升序排序时。
方法2(比赛法) 将阵列分成两部分,比较两部分的最大值和最小值,得到整个阵列的最大值和最小值。
Pair MaxMin(array, array_size) if array_size = 1 return element as both max and min else if arry_size = 2 one comparison to determine max and min return that pair else /* array_size > 2 */ recur for max and min of left half recur for max and min of right half one comparison determines true max of the two candidates one comparison determines true min of the two candidates return the pair of max and min
实施
C++
// C++ program of above implementation #include<iostream> using namespace std; // structure is used to return // two values from minMax() struct Pair { int min; int max; }; struct Pair getMinMax( int arr[], int low, int high) { struct Pair minmax, mml, mmr; int mid; // If there is only one element if (low == high) { minmax.max = arr[low]; minmax.min = arr[low]; return minmax; } // If there are two elements if (high == low + 1) { if (arr[low] > arr[high]) { minmax.max = arr[low]; minmax.min = arr[high]; } else { minmax.max = arr[high]; minmax.min = arr[low]; } return minmax; } // If there are more than 2 elements mid = (low + high) / 2; mml = getMinMax(arr, low, mid); mmr = getMinMax(arr, mid + 1, high); // Compare minimums of two parts if (mml.min < mmr.min) minmax.min = mml.min; else minmax.min = mmr.min; // Compare maximums of two parts if (mml.max > mmr.max) minmax.max = mml.max; else minmax.max = mmr.max; return minmax; } // Driver code int main() { int arr[] = { 1000, 11, 445, 1, 330, 3000 }; int arr_size = 6; struct Pair minmax = getMinMax(arr, 0, arr_size - 1); cout << "Minimum element is " << minmax.min << endl; cout << "Maximum element is " << minmax.max; return 0; } // This code is contributed by nik_3112 |
C
/* structure is used to return two values from minMax() */ #include<stdio.h> struct pair { int min; int max; }; struct pair getMinMax( int arr[], int low, int high) { struct pair minmax, mml, mmr; int mid; // If there is only one element if (low == high) { minmax.max = arr[low]; minmax.min = arr[low]; return minmax; } /* If there are two elements */ if (high == low + 1) { if (arr[low] > arr[high]) { minmax.max = arr[low]; minmax.min = arr[high]; } else { minmax.max = arr[high]; minmax.min = arr[low]; } return minmax; } /* If there are more than 2 elements */ mid = (low + high)/2; mml = getMinMax(arr, low, mid); mmr = getMinMax(arr, mid+1, high); /* compare minimums of two parts*/ if (mml.min < mmr.min) minmax.min = mml.min; else minmax.min = mmr.min; /* compare maximums of two parts*/ if (mml.max > mmr.max) minmax.max = mml.max; else minmax.max = mmr.max; return minmax; } /* Driver program to test above function */ int main() { int arr[] = {1000, 11, 445, 1, 330, 3000}; int arr_size = 6; struct pair minmax = getMinMax(arr, 0, arr_size-1); printf ( "nMinimum element is %d" , minmax.min); printf ( "nMaximum element is %d" , minmax.max); getchar (); } |
JAVA
// Java program of above implementation public class GFG { /* Class Pair is used to return two values from getMinMax() */ static class Pair { int min; int max; } static Pair getMinMax( int arr[], int low, int high) { Pair minmax = new Pair(); Pair mml = new Pair(); Pair mmr = new Pair(); int mid; // If there is only one element if (low == high) { minmax.max = arr[low]; minmax.min = arr[low]; return minmax; } /* If there are two elements */ if (high == low + 1 ) { if (arr[low] > arr[high]) { minmax.max = arr[low]; minmax.min = arr[high]; } else { minmax.max = arr[high]; minmax.min = arr[low]; } return minmax; } /* If there are more than 2 elements */ mid = (low + high) / 2 ; mml = getMinMax(arr, low, mid); mmr = getMinMax(arr, mid + 1 , high); /* compare minimums of two parts*/ if (mml.min < mmr.min) { minmax.min = mml.min; } else { minmax.min = mmr.min; } /* compare maximums of two parts*/ if (mml.max > mmr.max) { minmax.max = mml.max; } else { minmax.max = mmr.max; } return minmax; } /* Driver program to test above function */ public static void main(String args[]) { int arr[] = { 1000 , 11 , 445 , 1 , 330 , 3000 }; int arr_size = 6 ; Pair minmax = getMinMax(arr, 0 , arr_size - 1 ); System.out.printf( "Minimum element is %d" , minmax.min); System.out.printf( "Maximum element is %d" , minmax.max); } } |
蟒蛇3
# Python program of above implementation def getMinMax(low, high, arr): arr_max = arr[low] arr_min = arr[low] # If there is only one element if low = = high: arr_max = arr[low] arr_min = arr[low] return (arr_max, arr_min) # If there is only two element elif high = = low + 1 : if arr[low] > arr[high]: arr_max = arr[low] arr_min = arr[high] else : arr_max = arr[high] arr_min = arr[low] return (arr_max, arr_min) else : # If there are more than 2 elements mid = int ((low + high) / 2 ) arr_max1, arr_min1 = getMinMax(low, mid, arr) arr_max2, arr_min2 = getMinMax(mid + 1 , high, arr) return ( max (arr_max1, arr_max2), min (arr_min1, arr_min2)) # Driver code arr = [ 1000 , 11 , 445 , 1 , 330 , 3000 ] high = len (arr) - 1 low = 0 arr_max, arr_min = getMinMax(low, high, arr) print ( 'Minimum element is ' , arr_min) print ( 'nMaximum element is ' , arr_max) # This code is contributed by DeepakChhitarka |
C#
// C# implementation of the approach using System; public class GFG { /* Class Pair is used to return two values from getMinMax() */ public class Pair { public int min; public int max; } static Pair getMinMax( int []arr, int low, int high) { Pair minmax = new Pair(); Pair mml = new Pair(); Pair mmr = new Pair(); int mid; // If there is only one element if (low == high) { minmax.max = arr[low]; minmax.min = arr[low]; return minmax; } /* If there are two elements */ if (high == low + 1) { if (arr[low] > arr[high]) { minmax.max = arr[low]; minmax.min = arr[high]; } else { minmax.max = arr[high]; minmax.min = arr[low]; } return minmax; } /* If there are more than 2 elements */ mid = (low + high) / 2; mml = getMinMax(arr, low, mid); mmr = getMinMax(arr, mid + 1, high); /* compare minimums of two parts*/ if (mml.min < mmr.min) { minmax.min = mml.min; } else { minmax.min = mmr.min; } /* compare maximums of two parts*/ if (mml.max > mmr.max) { minmax.max = mml.max; } else { minmax.max = mmr.max; } return minmax; } /* Driver program to test above function */ public static void Main(String []args) { int []arr = {1000, 11, 445, 1, 330, 3000}; int arr_size = 6; Pair minmax = getMinMax(arr, 0, arr_size - 1); Console.Write( "Minimum element is {0}" , minmax.min); Console.Write( "Maximum element is {0}" , minmax.max); } } // This code contributed by Rajput-Ji |
Javascript
<script> // Javascript program of above implementation /* Class Pair is used to return two values from getMinMax() */ class Pair { constructor(){ this .min = -1; this .max = 10000000; } } function getMinMax(arr , low , high) { var minmax = new Pair(); var mml = new Pair(); var mmr = new Pair(); var mid; // If there is only one element if (low == high) { minmax.max = arr[low]; minmax.min = arr[low]; return minmax; } /* If there are two elements */ if (high == low + 1) { if (arr[low] > arr[high]) { minmax.max = arr[low]; minmax.min = arr[high]; } else { minmax.max = arr[high]; minmax.min = arr[low]; } return minmax; } /* If there are more than 2 elements */ mid = parseInt((low + high) / 2); mml = getMinMax(arr, low, mid); mmr = getMinMax(arr, mid + 1, high); /* compare minimums of two parts */ if (mml.min < mmr.min) { minmax.min = mml.min; } else { minmax.min = mmr.min; } /* compare maximums of two parts */ if (mml.max > mmr.max) { minmax.max = mml.max; } else { minmax.max = mmr.max; } return minmax; } /* Driver program to test above function */ var arr = [ 1000, 11, 445, 1, 330, 3000 ]; var arr_size = 6; var minmax = getMinMax(arr, 0, arr_size - 1); document.write( "Minimum element is " , minmax.min); document.write( "<br/>Maximum element is " , minmax.max); // This code is contributed by Rajput-Ji </script> |
输出:
Minimum element is 1Maximum element is 3000
时间复杂性: O(n)
比较总数:让比较数为T(n)。T(n)可以写成如下: 算法范式:分而治之
T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2 T(2) = 1 T(1) = 0
如果n是2的幂,那么我们可以把T(n)写成:
T(n) = 2T(n/2) + 2
在解决上述递归之后,我们得到
T(n) = 3n/2 -2
因此,如果n是2的幂,则该方法进行3n/2-2比较。如果n不是2的幂,它会进行3n/2-2以上的比较。
方法3(成对比较) 如果n为奇数,则将min和max初始化为第一个元素。 如果n为偶数,则分别将最小值和最大值初始化为前两个元素的最小值和最大值。 对于其余的元素,两人一组选择它们,并比较它们之间的差异 最大值和最小值分别为最大值和最小值。
C++
// C++ program of above implementation #include<iostream> using namespace std; // Structure is used to return // two values from minMax() struct Pair { int min; int max; }; struct Pair getMinMax( int arr[], int n) { struct Pair minmax; int i; // If array has even number of elements // then initialize the first two elements // as minimum and maximum if (n % 2 == 0) { if (arr[0] > arr[1]) { minmax.max = arr[0]; minmax.min = arr[1]; } else { minmax.min = arr[0]; minmax.max = arr[1]; } // Set the starting index for loop i = 2; } // If array has odd number of elements // then initialize the first element as // minimum and maximum else { minmax.min = arr[0]; minmax.max = arr[0]; // Set the starting index for loop i = 1; } // In the while loop, pick elements in // pair and compare the pair with max // and min so far while (i < n - 1) { if (arr[i] > arr[i + 1]) { if (arr[i] > minmax.max) minmax.max = arr[i]; if (arr[i + 1] < minmax.min) minmax.min = arr[i + 1]; } else { if (arr[i + 1] > minmax.max) minmax.max = arr[i + 1]; if (arr[i] < minmax.min) minmax.min = arr[i]; } // Increment the index by 2 as // two elements are processed in loop i += 2; } return minmax; } // Driver code int main() { int arr[] = { 1000, 11, 445, 1, 330, 3000 }; int arr_size = 6; Pair minmax = getMinMax(arr, arr_size); cout << "nMinimum element is " << minmax.min << endl; cout << "nMaximum element is " << minmax.max; return 0; } // This code is contributed by nik_3112 |
C
#include<stdio.h> /* structure is used to return two values from minMax() */ struct pair { int min; int max; }; struct pair getMinMax( int arr[], int n) { struct pair minmax; int i; /* If array has even number of elements then initialize the first two elements as minimum and maximum */ if (n%2 == 0) { if (arr[0] > arr[1]) { minmax.max = arr[0]; minmax.min = arr[1]; } else { minmax.min = arr[0]; minmax.max = arr[1]; } i = 2; /* set the starting index for loop */ } /* If array has odd number of elements then initialize the first element as minimum and maximum */ else { minmax.min = arr[0]; minmax.max = arr[0]; i = 1; /* set the starting index for loop */ } /* In the while loop, pick elements in pair and compare the pair with max and min so far */ while (i < n-1) { if (arr[i] > arr[i+1]) { if (arr[i] > minmax.max) minmax.max = arr[i]; if (arr[i+1] < minmax.min) minmax.min = arr[i+1]; } else { if (arr[i+1] > minmax.max) minmax.max = arr[i+1]; if (arr[i] < minmax.min) minmax.min = arr[i]; } i += 2; /* Increment the index by 2 as two elements are processed in loop */ } return minmax; } /* Driver program to test above function */ int main() { int arr[] = {1000, 11, 445, 1, 330, 3000}; int arr_size = 6; struct pair minmax = getMinMax (arr, arr_size); printf ( "nMinimum element is %d" , minmax.min); printf ( "nMaximum element is %d" , minmax.max); getchar (); } |
JAVA
// Java program of above implementation public class GFG { /* Class Pair is used to return two values from getMinMax() */ static class Pair { int min; int max; } static Pair getMinMax( int arr[], int n) { Pair minmax = new Pair(); int i; /* If array has even number of elements then initialize the first two elements as minimum and maximum */ if (n % 2 == 0 ) { if (arr[ 0 ] > arr[ 1 ]) { minmax.max = arr[ 0 ]; minmax.min = arr[ 1 ]; } else { minmax.min = arr[ 0 ]; minmax.max = arr[ 1 ]; } i = 2 ; /* set the starting index for loop */ } /* If array has odd number of elements then initialize the first element as minimum and maximum */ else { minmax.min = arr[ 0 ]; minmax.max = arr[ 0 ]; i = 1 ; /* set the starting index for loop */ } /* In the while loop, pick elements in pair and compare the pair with max and min so far */ while (i < n - 1 ) { if (arr[i] > arr[i + 1 ]) { if (arr[i] > minmax.max) { minmax.max = arr[i]; } if (arr[i + 1 ] < minmax.min) { minmax.min = arr[i + 1 ]; } } else { if (arr[i + 1 ] > minmax.max) { minmax.max = arr[i + 1 ]; } if (arr[i] < minmax.min) { minmax.min = arr[i]; } } i += 2 ; /* Increment the index by 2 as two elements are processed in loop */ } return minmax; } /* Driver program to test above function */ public static void main(String args[]) { int arr[] = { 1000 , 11 , 445 , 1 , 330 , 3000 }; int arr_size = 6 ; Pair minmax = getMinMax(arr, arr_size); System.out.printf( "Minimum element is %d" , minmax.min); System.out.printf( "Maximum element is %d" , minmax.max); } } |
蟒蛇3
# Python3 program of above implementation def getMinMax(arr): n = len (arr) # If array has even number of elements then # initialize the first two elements as minimum # and maximum if (n % 2 = = 0 ): mx = max (arr[ 0 ], arr[ 1 ]) mn = min (arr[ 0 ], arr[ 1 ]) # set the starting index for loop i = 2 # If array has odd number of elements then # initialize the first element as minimum # and maximum else : mx = mn = arr[ 0 ] # set the starting index for loop i = 1 # In the while loop, pick elements in pair and # compare the pair with max and min so far while (i < n - 1 ): if arr[i] < arr[i + 1 ]: mx = max (mx, arr[i + 1 ]) mn = min (mn, arr[i]) else : mx = max (mx, arr[i]) mn = min (mn, arr[i + 1 ]) # Increment the index by 2 as two # elements are processed in loop i + = 2 return (mx, mn) # Driver Code if __name__ = = '__main__' : arr = [ 1000 , 11 , 445 , 1 , 330 , 3000 ] mx, mn = getMinMax(arr) print ( "Minimum element is" , mn) print ( "Maximum element is" , mx) # This code is contributed by Kaustav |
C#
// C# program of above implementation using System; class GFG { /* Class Pair is used to return two values from getMinMax() */ public class Pair { public int min; public int max; } static Pair getMinMax( int []arr, int n) { Pair minmax = new Pair(); int i; /* If array has even number of elements then initialize the first two elements as minimum and maximum */ if (n % 2 == 0) { if (arr[0] > arr[1]) { minmax.max = arr[0]; minmax.min = arr[1]; } else { minmax.min = arr[0]; minmax.max = arr[1]; } i = 2; } /* set the starting index for loop */ /* If array has odd number of elements then initialize the first element as minimum and maximum */ else { minmax.min = arr[0]; minmax.max = arr[0]; i = 1; /* set the starting index for loop */ } /* In the while loop, pick elements in pair and compare the pair with max and min so far */ while (i < n - 1) { if (arr[i] > arr[i + 1]) { if (arr[i] > minmax.max) { minmax.max = arr[i]; } if (arr[i + 1] < minmax.min) { minmax.min = arr[i + 1]; } } else { if (arr[i + 1] > minmax.max) { minmax.max = arr[i + 1]; } if (arr[i] < minmax.min) { minmax.min = arr[i]; } } i += 2; /* Increment the index by 2 as two elements are processed in loop */ } return minmax; } // Driver Code public static void Main(String []args) { int []arr = {1000, 11, 445, 1, 330, 3000}; int arr_size = 6; Pair minmax = getMinMax(arr, arr_size); Console.Write( "Minimum element is {0}" , minmax.min); Console.Write( "Maximum element is {0}" , minmax.max); } } // This code is contributed by 29AjayKumar |
输出:
Minimum element is 1Maximum element is 3000
时间复杂性: O(n)
比较总数:奇偶n不同,见下表:
If n is odd: 3*(n-1)/2 If n is even: 1 Initial comparison for initializing min and max, and 3(n-2)/2 comparisons for rest of the elements = 1 + 3*(n-2)/2 = 3n/2 -2
当n是2的幂时,第二种和第三种方法的比较次数相等。 总的来说,方法3似乎是最好的。 如果您发现上述程序/算法中存在任何缺陷,或者有更好的方法来解决相同的问题,请写下评论。