用C语言写一个找第二大的代码并体现分治思想
时间: 2024-05-08 19:15:26 浏览: 8
以下是一个使用分治思想的C语言代码,用于找到一个整数数组中第二大的数:
```c
#include <stdio.h>
int findSecondLargest(int arr[], int left, int right) {
if (left == right) { // 只有一个元素
return arr[left];
} else if (left + 1 == right) { // 只有两个元素
return arr[left] > arr[right] ? arr[left] : arr[right];
} else {
int mid = (left + right) / 2;
int maxLeft = findSecondLargest(arr, left, mid);
int maxRight = findSecondLargest(arr, mid + 1, right);
return maxLeft > maxRight ? maxLeft : maxRight;
}
}
int main() {
int arr[] = { 3, 5, 2, 7, 8, 1, 9, 4 };
int size = sizeof(arr) / sizeof(arr[0]);
int max = findSecondLargest(arr, 0, size - 1);
int secondMax = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] < max && arr[i] > secondMax) {
secondMax = arr[i];
}
}
printf("第二大的数是:%d\n", secondMax);
return 0;
}
```
该代码使用了递归的方式进行分治,将数组分成左右两部分,分别找出左半部分和右半部分中的最大值,然后比较这两个最大值,返回其中较大的一个。最后,在找到最大值的基础上,再遍历一遍数组,找到比最大值小但是比其它元素大的数,即为第二大的数。