// 题目：从数组中找出最大的数和最小的数
// 解法1：将其看作两个独立的问题，采用“打擂台”的方式逐个比较，复杂度O(2N)
public class Main {
public static void main(String[] args) {
findMaxMinNum(new int[]{5,6,8,3,7,9});
}
public static void findMaxMinNum(int[] input) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0;i<input.length;i++){
if(input[i]>max){
max = input[i];
}
if(input[i]<min){
min = input[i];
}
}
System.out.println("max = "+max+", min = "+min);
}
}
//解法2：每次取两个元素，先让这两个元素进行比较，然后其中较大的与max比较，较小的与min比较，时间复杂度O(1.5N)
public class Main {
public static void main(String[] args) {
findMaxMinNum(new int[]{5,6,8,3,7,9});
}
public static void findMaxMinNum(int[] input) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0;i<input.length;i = i+2){//循环中每次取两个元素
if(i+1<input.length){//要判断第二个元素是否超出数组的长度
if(input[i+1]>input[i]){
if(input[i+1]>max){
max = input[i+1];
}
if(input[i]<min){
min = input[i];
}
}else{
if(input[i]>max){
max = input[i];
}
if(input[i+1]<min){
min = input[i+1];
}
}
}else{
if(input[i]>max){
max = input[i];
}
if(input[i]<min){
min = input[i];
}
}
}
System.out.println("max = "+max+", min = "+min);
}
}
//解法3：采用分治法和递归，两两分组，时间复杂度O(1.5N)
public class Main {
public static void main(String[] args) {
findMaxMinNum(new int[]{5,6,8,3,7,9});
}
public static void findMaxMinNum(int[] input) {
int max = searchMax(input, 0, input.length-1);
int min = searchMin(input, 0, input.length-1);
System.out.println("max = "+max+", min = "+min);
}
public static int searchMax(int[] input, int low, int high) {
if(high-low <= 1){
if(input[high]>input[low]){
return input[high];
}else{
return input[low];
}
}
int maxLeft = searchMax(input, low, low+(high-low)/2);
int maxRight = searchMax(input, low+(high-low)/2+1,high);
if(maxLeft>maxRight){
return maxLeft;
}else{
return maxRight;
}
}
public static int searchMin(int[] input, int low, int high) {
if(high-low <= 1){//因为可能出现不会两两分组的情况，比如有奇数个元素，如果那样，high == low，所以条件为<=而不是==
if(input[high]<input[low]){
return input[high];
}else{
return input[low];
}
}
int minLeft = searchMin(input, low, low+(high-low)/2);
int minRight = searchMin(input, low+(high-low)/2+1,high);
if(minLeft<minRight){
return minLeft;
}else{
return minRight;
}
}
}
//扩展问题：求最大和第二大的数
//解法：同样采用分治法和递归，两两分组，但记录最大和第二大的数，最后拿较大半区的第二大的数与两个半区中较小的最大数进行比较，决定第二大的数
public class Main {
public static void main(String[] args) {
findMaxMinNum(new int[]{5,6,8,3,7,9});
}
public static void findMaxMinNum(int[] input) {
List<Integer> result = searchMax(input, 0, input.length-1);
System.out.println("max = "+result.get(0)+", smax = "+result.get(1));
}
public static List<Integer> searchMax(int[] input, int low, int high) {
if(high-low == 1){
List<Integer> temp = new ArrayList<Integer>();
if(input[high]>input[low]){
temp.add(input[high]);
temp.add(input[low]);
return temp;
}else{
temp.add(input[low]);
temp.add(input[high]);
return temp;
}
}
if(high-low == 0){//右边数字只有一个的情况
List<Integer> temp = new ArrayList<Integer>();
temp.add(input[high]);
return temp;
}
List<Integer> left = searchMax(input, low, low+(high-low)/2);
List<Integer> right = searchMax(input, low+(high-low)/2+1,high);
List<Integer> result = new ArrayList<Integer>();
if(right.size() == 1){//右边数字只有一个的情况
if(left.get(0)>right.get(0)){
result.add(left.get(0));
if(left.get(1)>right.get(0)){
result.add(left.get(1));
}else{
result.add(right.get(0));
}
}else{
result.add(right.get(0));
result.add(left.get(0));
}
return result;
}
if(left.get(0)>right.get(0)){//正常比较，存储最大和第二大的数
result.add(left.get(0));
if(left.get(1)>right.get(0)){
result.add(left.get(1));
}else{
result.add(right.get(0));
}
return result;
}else{
result.add(right.get(0));
if(right.get(1)>left.get(0)){
result.add(right.get(1));
}else{
result.add(left.get(0));
}
return result;
}
}
}
