用C＋＋找出数组中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数

在C++中，找出数组中既不是最大值也不是最小值的元素可以使用分治法或者排序+遍历的方式。这里我们选择后者，因为它通常需要更少的比较次数。

首先，对数组进行一次排序，这一步是最坏情况下的比较次数，因为最坏情况下，如果数组已经完全逆序，我们需要n(n-1)/2次比较才能完成排序，其中n是数组长度。使用快速排序、归并排序等平均时间复杂度为O(n log n)的算法。

然后从排序后的中间位置开始遍历，取中间元素（对于偶数长度的数组取中间两个元素的平均值）。这个中间元素通常既不会是最大值也不会是最小值。

以下是简化版的伪代码：

// 假设数组arr已排序
int findMedian(int arr[], int n)
{
    if (n % 2 == 0)
        return (arr[n / 2 - 1] + arr[n / 2]) / 2; // 对于偶数长度，选择中间两个数的平均值
    else
        return arr[n / 2]; // 对于奇数长度，中间的就是既不是最大也不是最小的
}

int main()
{
    // ... 实现排序，如快速排序 ...
    // 调用findMedian(arr, n);
    // ... 回溯到未排序状态 ...
}

相关问题

用C++找出数组中一个既不是最大也不是最小的元素

在C++中，要找出数组中既不是最大值也不是最小值的元素，可以采用分而治之的思想，将数组分为两部分，然后分别找到每部分的最大值和最小值，再在这两个边界之外查找中间元素。下面是一个简单的示例，假设已知数组长度并有额外的空间存放临时变量：

#include <iostream>
using namespace std;

int findNonExtremal(int arr[], int left, int right) {
    if (left >= right) // 如果只有一个元素，那么它既是最大也是最小
        return -1; // 返回一个特殊的值表示没有这样的元素

    int mid = left + (right - left) / 2;
    int max_left = (arr[mid] > arr[left]) ? mid : left;
    int min_right = (arr[mid] < arr[right]) ? mid : right;

    for (int i = max_left + 1; i <= min_right - 1; i++) {
        if (arr[i] != arr[max_left] && arr[i] != arr[min_right])
            return i; // 找到符合条件的元素
    }

    // 如果所有中间元素都是极端值，返回下一个非极端元素
    return (max_left == right - 1) ? left : right;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = findNonExtremal(arr, 0, n - 1);
    if (result != -1)
        cout << "A non-extremal element is: " << arr[result];
    else
        cout << "No such element exists in the array.";
    return 0;
}

这个程序会返回数组中第一个既不是最大也不是最小的元素。如果找不到这样的元素，就会返回-1。

设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小 的元素,并说明最坏情况下的比较次数。 要求分别给出伪代码和C++描述

伪代码：

(1) 从数组a[1..n]的第1个元素开始，到第n个元素为止，找到其中最大值和最小值，并将它们分别存储在max和min变量中。

(2) 从数组a[1..n]的第1个元素开始，到第n个元素为止，找到一个既不是最大也不是最小的元素，并将它存储在mid变量中。

(3) 返回mid变量的值。

C 描述：

int findMid(int a[], int n) {
int max = a[0], min = a[0], mid, i;
for (i = 1; i < n; i++) {
if (a[i] > max) {
max = a[i];
}
if (a[i] < min) {
min = a[i];
}
}
for (i = 0; i < n; i++) {
if (a[i] != max && a[i] != min) {
mid = a[i];
break;
}
}
return mid;
}

最坏情况下的比较次数：

最坏情况下是需要遍历整个数组两次，因此比较次数为2n-2。