Блог

Главная - Вопросы по программированию - Поиск k-го наименьшего элемента в массиве с помощью двоичного дерева поиска

Поиск k-го наименьшего элемента в массиве с помощью двоичного дерева поиска

#c #arrays #sorting #search #binary-search-tree

#c #массивы #сортировка #Поиск #binary-search-tree

Вопрос:

Вопрос в том, чтобы найти «K-й» наименьший элемент в массиве. https://practice.geeksforgeeks.org/problems/kth-smallest-element/0

Теперь я видел приведенные методы, но не могу понять их должным образом. Моя первая ИНТУИЦИЯ после того, как было создать по британскому летнему времени от данного массива и использование симметричного обхода по британскому летнему времени, чтобы найти «КТН» наименьшего элемента массива. Вот код моего подхода.

/*

 #include <bits/stdc  .h>
using namespace std;
struct node{
    int data;
    node* left;
    node* right;
};
vector<int> v;//sorted vector
node* insert(node* root,int data){
    if(!root){
        root = new node();
        root->data = data;
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    if(root->data > data)
    root->left = insert(root->left , data);
    else
    root->right = insert(root->right , data);
    
    return root;
}
void inOrder(node* root){
    if(!root)
    return;
    
    inOrder(root->left);
    v.push_back(root->data);
    //cout<<root->data<<" ";
    inOrder(root->right);
}
int main() {
    int t;
    cin>>t;
    while(t--){
        node* root = NULL;
        int n,el;
        cin>>n;
        for(int i=0;i<n;i  ){
            cin>>el;
            root = insert(root,el);
        }
        int k;
        cin>>k;
        inOrder(root);
        cout<<v[k-1]<<endl;
        v.clear();
    }
    return 0;
}

*/
Теперь, по моему мнению, это должно быть O (n) в худшем случае, но я не уверен. Этот код дает мне «TLE». Помогите мне исправить этот код. Это, наверное, первый раз у меня есть интуиция, чтобы решить вопрос с помощью по британскому летнему времени, поэтому я хотел бы завершить этот вопрос только через такой подход.

Комментарии:

1. Ваш код не O (n), а O (n * 2) в худшем случае и O (n * log n) в среднем. Я ожидаю, что TLE происходит с данными, намеренно выбранными для выявления поведения в наихудшем случае. В худшем случае случится с (например) уже отсортированные данные, когда свои по британскому летнему времени будет вырождается в связанный список. Это хорошо известная проблема с по британскому летнему времени. Хорошей новостью является то, что код кажется правильным, если он неэффективен.

2. И почему это O (n ^ 2)? Это потому, что каждая вставка равна O (n), и вызов ее ‘n’ раз делает ее O (n ^ 2)? Значит, этот подход нельзя использовать?

3. Вот и все, с отсортированными данными это то, что произойдет.

4. Опечатка в комментарии выше. Конечно, я имел в виду O (n ^ 2), то есть квадратичное время, а не O (n * 2).

5. nth_element равно O (n), вы могли бы просто использовать это.

Ответ №1:

Вы просто не можете решить этот вопрос С по британскому летнему времени.

Вопрос Клири утверждает, что ожидаемая временная сложность: O (N).

Но сама операция вставки занимает среднее значение O (logN), худшее O (N).ССЫЛКА
Вы выполняете операцию вставки N раз. Следовательно,

 for(int i=0;i<n;i  ){
  cin>>el;
  root = insert(root,el);
}

Этот фрагмент кода уже занял O (NlogN) или худший O (N ^ 2).

Лучшим решением является использование pivot и разбиения на разделы, как и быстрая сортировка.

Но вместо полной сортировки массивов вы отбрасываете один раздел, который не имеет значения, и продолжаете рекурсивное разбиение только на один раздел.

Проверьте ссылку на лучшее решение для получения подробной информации.