Question

Язык: C++ Дано:Неупорядоченный массив arr из n натуральных чисел.Индекс j (1<=j<=n)Требуется найти такое число, которое при упорядоченном по убыванию массиве находилось на arr[j-1].Запрещено создавать новые и упорядочивать старый массив.

Answer 1

#include <iostream>

using namespace std;

int main() {

 int n,j,mnt,mn,mx;

 cout<<"n = "; cin>>n;

 int arr[n];

 cout<<"array: "; cin>>arr[0];

 mn=arr[0]; mx=mn;  

 for (int i=1; i<n; i++) {

    cin>>arr[i];

    if (arr[i]<mn) mn=arr[i];

    if (arr[i]>mx) mx=arr[i];

 }

 mnt=mn;  

 cout<<"j = "; cin>>j;

 for (int i=2; i<=j; i++) {

    mn=mx;

    for (int k=0; k<n; k++)

       if ((arr[k]>mnt) && (arr[k]<mn)) mn=arr[k];

    mnt=mn;

 }

 cout<<mn<<endl;    

 system("pause");

 return 0;

}

Ввод - вывод:

n = 10

array: 11 -5 15 -8 13 -10 19 36 5 9

j = 5

9

Answer 2

Для решения этой задачи можно воспользоваться алгоритмом поиска k-ой порядковой статистики, который работает за линейное время O(n).

Сначала нужно найти максимальный элемент в массиве arr. Затем создать новый массив freq, где freq[i] будет равен количеству элементов, которые больше или равны i в массиве arr. Например, если в arr есть 3 элемента, которые больше или равны 5, то freq[5] = 3.

Затем можно использовать следующий алгоритм для нахождения числа, которое находится на arr[j-1] в упорядоченном по убыванию массиве:

1. Инициализировать переменные k = n - j + 1 и i = 0.
2. Пока i < n и k > 0, выполнять следующие шаги:
   • Найти максимальный элемент в массиве arr.
   • Уменьшить k на freq[max], где max - найденный максимальный элемент.
   • Установить freq[max] в 0.
   • Если k <= 0, вернуть max.
   • Увеличить i на 1.

Этот алгоритм находит k-ую порядковую статистику (элемент, который находится на позиции k при сортировке массива по убыванию). Поскольку j = n - k + 1, можно найти число, которое находится на arr[j-1], как элемент, который находится на позиции n - k - 1 в отсортированном массиве.

Пример реализации на C++:

cppCopy code
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n, j;
    cin >> n >> j;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // Находим максимальный элемент
    int max_elem = *max_element(arr.begin(), arr.end());

    // Создаем массив частот
    vector<int> freq(max_elem + 1, 0);
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }
    for (int i = 1; i <= max_elem; i++) {
        freq[i] += freq[i-1];
    }

    // Находим k-ую порядковую статистику
    int k = n - j + 1;
    int i = 0;
    while (i < n && k > 0) {
        int max_val = max_elem;
        while (freq[max_val] == 0) {
            max_val--;
        }
        k -= freq[max_val];
        freq[max_val] = 0;
        if (k <= 0) {
            cout << max_val << endl;
            break;
        }
        i++;
    }
    return 0;
}