单链表C ++的Lomuto分区方案

Question

我需要一种算法，可以找到线性时间复杂度O（n）和恒定空间复杂度O（1）中单链表的中位数。

编辑：单链接列表是C样式的单链接列表。不允许stl（没有容器，没有函数，禁止所有stl，例如没有std :: forward_list）。不允许将数字移动到任何其他容器（如数组）中。O（logn）的空间复杂度是可以接受的，因为对于我的列表来说，实际上甚至小于100。另外，我也不允许使用STL函数，例如nth_element

[基本上，我将链表与3 * 10 ^ 6元素相连，我需要在3秒内获得中值，所以我不能使用排序算法对列表进行排序（这将是O（nlogn），并且将大概10到14秒。

我已经在网上进行了一些搜索，发现可以通过quickselect在O（n）和O（1）空间完全性中找到std :: vector的中位数（最坏的情况是在O（n ^ 2）中，但很少），例如：https://www.geeksforgeeks.org/quickselect-a-simple-iterative-implementation/

但是我找不到用于链表的算法。问题是我可以使用数组索引随机访问向量。如果我想修改该算法，那么复杂度会更大，因为。例如，当我将数据透视索引更改为左侧时，我实际上需要遍历列表以获取该新元素并走得更远（这将使我至少O（kn）的列表中有一个大k，甚至推动O（n ^ 2）...）。

编辑2：

我知道我有太多的变量，但是我一直在测试不同的东西，而我仍在编写代码...我当前的代码：

#include <bits/stdc++.h>

using namespace std;

template <class T> class Node {
    public:
    T data;
    Node<T> *next;
};

template <class T> class List {
    public:
    Node<T> *first;
};

template <class T> T getMedianValue(List<T> & l) {
    Node<T> *crt,*pivot,*incpivot;
    int left, right, lung, idx, lungrel,lungrel2, left2, right2, aux, offset;
    pivot = l.first;
    crt = pivot->next;
    lung = 1;
//lung is the lenght of the linked list (yeah it's lenght in romanian...)
//lungrel and lungrel2 are the relative lenghts of the part of 
//the list I am processing, e.g: 2 3 4 in a list with 1 2 3 4 5
    right = left = 0;
    while (crt != NULL) { 
        if(crt->data < pivot->data){
            aux = pivot->data;
            pivot->data = crt->data;
            crt->data = pivot->next->data;
            pivot->next->data = aux;
            pivot = pivot->next;
            left++;
        }
        else right++;
       // cout<<crt->data<<endl;
        crt = crt->next; 
        lung++; 
    }
    if(right > left) offset = left;
//  cout<<endl;
//  cout<<pivot->data<<" "<<left<<" "<<right<<endl;
//  printList(l);
//  cout<<endl;
    lungrel = lung;
    incpivot = l.first;
   // offset = 0;
    while(left != right){
        //cout<<"parcurgere"<<endl;
        if(left > right){
            //cout<<endl;
            //printList(l);
            //cout<<endl;
            //cout<<"testleft "<<incpivot->data<<" "<<left<<" "<<right<<endl;
            crt = incpivot->next;
            pivot = incpivot;
            idx = offset;left2 = right2 = lungrel = 0;
            //cout<<idx<<endl;
            while(idx < left && crt!=NULL){
                 if(pivot->data > crt->data){
                   //  cout<<"1crt "<<crt->data<<endl;
                     aux = pivot->data;
                     pivot->data = crt->data;
                     crt->data = pivot->next->data;
                     pivot->next->data = aux;
                     pivot = pivot->next;
                     left2++;lungrel++;
                  }
                  else {
                      right2++;lungrel++;
                      //cout<<crt->data<<" "<<right2<<endl;
                  }
                  //cout<<crt->data<<endl;
                  crt = crt->next;
                  idx++;
             }
             left = left2 + offset;
             right = lung - left - 1;
             if(right > left) offset = left;
             //if(pivot->data == 18) return 18;
             //cout<<endl;
             //cout<<"l "<<pivot->data<<" "<<left<<" "<<right<<" "<<right2<<endl;
           //  printList(l);
        }
        else if(left < right && pivot->next!=NULL){
            idx = left;left2 = right2 = 0;
            incpivot = pivot->next;offset++;left++;
            //cout<<endl;
            //printList(l);
            //cout<<endl;
            //cout<<"testright "<<incpivot->data<<" "<<left<<" "<<right<<endl;
            pivot = pivot->next;
            crt = pivot->next;
            lungrel2 = lungrel;
            lungrel = 0;
           // cout<<"p right"<<pivot->data<<" "<<left<<" "<<right<<endl;
            while((idx < lungrel2 + offset - 1) && crt!=NULL){
                 if(crt->data < pivot->data){
                //     cout<<"crt "<<crt->data<<endl;
                     aux = pivot->data;
                     pivot->data = crt->data;
                     crt->data = (pivot->next)->data;
                     (pivot->next)->data = aux;
                     pivot = pivot->next;
                 //    cout<<"crt2 "<<crt->data<<endl;
                     left2++;lungrel++;
                  }
                  else right2++;lungrel++;
                  //cout<<crt->data<<endl;
                  crt = crt->next;
                  idx++;
             }
             left = left2 + left;
             right = lung - left - 1;
                 if(right > left) offset = left;
            // cout<<"r "<<pivot->data<<" "<<left<<" "<<right<<endl;
           //  printList(l);
        }
        else{
            //cout<<cmx<<endl;
            return pivot->data;
        }
    }
    //cout<<cmx<<endl;
    return pivot->data;
}
template <class T> void printList(List<T> const & l) {
    Node<T> *tmp;
    if(l.first != NULL){
        tmp = l.first;
        while(tmp != NULL){
            cout<<tmp->data<<" ";
            tmp = tmp->next;
        }
    }
}
template <class T> void push_front(List<T> & l, int x)
{
    Node<T>* tmp = new Node<T>;

    tmp->data = x;

    tmp->next = l.first;
    l.first = tmp;
}

int main(){
    List<int> l;
    int n = 0;
    push_front(l, 19);
    push_front(l, 12);
    push_front(l, 11);
    push_front(l, 101);
    push_front(l, 91);
    push_front(l, 21);
    push_front(l, 9);
    push_front(l, 6);
    push_front(l, 25);
    push_front(l, 4);
    push_front(l, 18);
    push_front(l, 2);
    push_front(l, 8);
    push_front(l, 10);
    push_front(l, 200);
    push_front(l, 225);
    push_front(l, 170);
    printList(l);
    n=getMedianValue(l);
    cout<<endl;
    cout<<n;

    return 0;
}

您是否对如何使quickselect适应可能适用于我的问题的单列出的链接或其他算法有任何建议？

Answer 1

所以您可以做的是使用迭代器来保持职位。我已经编写了上面与std :: forward_list一起使用的算法。我知道这不是完美的方法，但请尽快写下来，希望对您有所帮助。

    int partition(int leftPos, int rightPos, std::forward_list<int>::iterator& currIter, 
    std::forward_list<int>::iterator lowIter, std::forward_list<int>::iterator highIter) {
        auto iter = lowIter;
        int i = leftPos - 1;
        for(int j = leftPos; j < rightPos - 1; j++) {
           if(*iter <= *highIter) {
               ++currIter;
               ++i;
               std::iter_swap(currIter, iter);
           }
           iter++;
        }
        std::forward_list<int>::iterator newIter = currIter;
        std::iter_swap(++newIter, highIter);
        return i + 1;
    }

   std::forward_list<int>::iterator kthSmallest(std::forward_list<int>& list, 
   std::forward_list<int>::iterator left, std::forward_list<int>::iterator right, int size, int k) {
       int leftPos {0};
       int rightPos {size};
       int pivotPos {0};

       std::forward_list<int>::iterator resetIter = left;
       std::forward_list<int>::iterator currIter = left;
       ++left;
       while(leftPos <= rightPos) {
           pivotPos = partition(leftPos, rightPos, currIter, left, right);

           if(pivotPos == (k-1)) {
               return currIter;
           } else if(pivotPos > (k-1)) {
               right = currIter;
               rightPos = pivotPos - 1;
           } else {
               left = currIter;
               ++left;
               resetIter = left;
               ++left;
               leftPos = pivotPos + 1;
           }

           currIter = resetIter;
       }

       return list.end();
  }

单链表C ++的Lomuto分区方案

问题描述投票：1回答：2

2个回答

最新问题

单链表C ++的Lomuto分区方案

问题描述 投票：1回答：2

2个回答

最新问题

问题描述投票：1回答：2