【笔记】数据结构刷题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;}
};