【笔记】数据结构刷题09

快速排序 215. 数组中的第K个最大元素

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
    
       return divide(nums,0,nums.size()-1,nums.size()-k);
       
    }

    int divide(vector<int>& nums,int left,int right,int k){
      if(left==right)return nums[k];
      int partition = nums[left],i=left-1,j=right+1;
      while(i<j){
        while(nums[++i]<partition);
        while(nums[--j]>partition);
        if(i<j)swap(nums[i],nums[j]);
      }
      if(k<=j)return divide(nums,left,j,k);
      else return divide(nums,j+1,right,k);
        
    }
};


/**

  if(left<=right)return ;
        int pivot = nums[left];
        int flag=0;
        int i=left,j=right;
        while(i<=j){
            if(flag==0){
                if(nums[j]<pivot){
                    nums[i]=nums[j];
                    i++;
                    flag=1;
                }else{
                    j--;
                }
            }
            if(flag==1){
                if(nums[i]>pivot){
                    nums[j]=nums[i];
                    j--;
                    flag=0;
                }else{
                    i++;
                }
            }

        }
        if(i==k-1){
            sample=pivot;
        }
        else{
            nums[i]=pivot;
        }
        divide(nums,left,i-1,k,sample);
        divide(nums,i+1,right,k,sample);
**/

链表的快速排序

参考链接

1. 建立3个辅助链表left，mid和right。
2. 将原始链表的头结点的值定为pivot，遍历原始链表，值等于pivot的节点插入mid末尾，小于pivot的插入left末尾，大于pivot的插入right末尾。
3. 递归处理left和right。
4. 将left，mid，right依次连接即可。

//超出时间的方法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
ListNode * getTail(ListNode* head){
    while(head->next!=nullptr)head=head->next;
    return head;
}
    ListNode* sortList(ListNode* head) {
        if(head==nullptr||head->next==nullptr)return head;
        auto left = new ListNode(-1);
        auto lTail = left;
    
        auto mid = new ListNode(-1);
        auto midTail = mid;

        auto right = new ListNode(-1);
        auto rTail=right;

        int val = head->val;
        for(auto cur=head;cur!=nullptr;cur=cur->next){
            if(cur->val<val){
                lTail->next = cur;
                lTail = lTail->next;
            }else if(cur->val==val){
                midTail->next=cur;
                midTail=midTail->next;
            }else{
                rTail->next = cur;
                rTail=rTail->next;
            }
        }
        lTail->next=nullptr;
        midTail->next = nullptr;
        rTail->next=nullptr;

        left->next=sortList(left->next);
        right->next=sortList(right->next);
        
        getTail(left)->next = mid->next;
        midTail->next = right->next;

        auto p =left->next;
        delete right;
        delete mid;
        delete left;
        return p;


        
    }
};