Skip to content

Latest commit

 

History

History
740 lines (572 loc) · 19.2 KB

排序.md

File metadata and controls

740 lines (572 loc) · 19.2 KB
Raw

排序总结

摆动排序II

LeetCode中文

题解：快速选择 + 数组反序穿插

详见：https://leetcode.cn/problems/wiggle-sort-ii/solutions/45144/yi-bu-yi-bu-jiang-shi-jian-fu-za-du-cong-onlognjia/

颜色分类

LeetCode中文

LeetCode英文

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶：

  • 一个直观的解决方案是使用计数排序的两趟扫描算法。首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
  • 你能想出一个仅使用常数空间的一趟扫描算法吗？

解答

方法1：计数排序

哈希表统计每个颜色代表的数字出现的次数，然后更新原数组，按照0,1,2各自的个数按照顺序赋值。

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        if(len == 0)
            return;
        
        vector<int> hash(3,0);
        for(int i=0;i<len;i++)
        {
            hash[nums[i]]++;
        }
        
        int j = 0;
        for(int i=0;i<3;i++)
        {
            while(hash[i] > 0)
            {
                nums[j++] = i;
                hash[i]--;
            }
        }
    }
};

方法2：荷兰国旗问题

定义两个指针，指针r指向数组开头前一个位置(代表红色)，指针b指向数组末尾后一个位置(代表蓝色)，然后从前向后遍历数组，对于遍历的每一个元素nums[w](w起始位置为0)，处理情况如下：

  1. 如果nums[w] == 0，则r后移一个位置，然后交换nums[r]和nums[w]的值，w后移一个位置；
  2. 如果nums[w] == 2，则b前移一个位置，然后交换nums[b]和nums[w]的值，w位置不变；
  3. 如果nums[w] == 1，则w后移一个位置。

直到w == b时，结束遍历。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int r = -1,w = 0,b = nums.size();
        while(w < b)
        {
            if(nums[w] == 0)
            {
                swap(nums[++r],nums[w++]);
            }
            else if(nums[w] == 2)
            {
                swap(nums[--b],nums[w]);
            }
            else
            {
                ++w;
            }
        }
        
    }
};

排序链表

LeetCode中文

LeetCode英文

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解答

方法1

归并排序 + 链表

  • 时间复杂度：O(n log n)
  • 空间复杂度：O(n)
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
         if(!head || !head->next) return head;
        
        ListNode *slow = head,*fast = head;
        while(fast && fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        ListNode *p1 = head,*p2 = slow->next;
        slow->next = nullptr;
        
        p1 = sortList(p1);
        p2 = sortList(p2);
        
        ListNode node(0),*head1 = &node;
        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                head1->next = p1;
                head1 = p1;
                p1 = p1->next;
            }
            else{
                head1->next = p2;
                head1 = p2;
                
                p2 = p2->next;
            }
        }
        
        if(p1)
            head1->next = p1;
        if(p2)
            head1->next = p2;
        
        return node.next;
    }
};

方法2

堆排序（优先级队列） + 链表

  • 时间复杂度：O(n log n)
  • 空间复杂度：O(n)
  1. 使用优先级队列priority_queue（底层用堆实现）
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
inline bool comp(const ListNode* p1,const ListNode* p2)
{
    return p1->val > p2->val;
}

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        priority_queue<ListNode*,vector<ListNode*>,decltype(comp)*> que(comp);
        ListNode* p = head;
        while(p)
        {
            que.push(p);
            p = p->next;
        }
        
        ListNode node(0),*head1 = &node;
        while(!que.empty())
        {
            auto tmp = que.top();
            que.pop();
            
            head1->next = tmp;
            head1 = head1->next;
        }
        
        head1->next = nullptr;
        
        return node.next;
    }
};
  1. 直接用STL中heap的接口：make_heap, push_heap ,pop_heap。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
inline bool comp(const ListNode* p1,const ListNode* p2)
{
    return p1->val > p2->val;
}

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector<ListNode*> vec;
        ListNode* p = head;
        while(p)
        {
            vec.push_back(p);
            p = p->next;
        }
        
        make_heap(vec.begin(),vec.end(),comp);
        
        ListNode node(0),*head1 = &node;
        while(!vec.empty())
        {
            auto tmp = vec.front();
            pop_heap(vec.begin(),vec.end(),comp);
            vec.pop_back();
            
            head1->next = tmp;
            head1 = head1->next;
        }
        
        head1->next = nullptr;
        
        return node.next;
    }
};

方法3 归并排序非递归

/**
 * 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* mergeSort(ListNode* head) {
      if (!head || !head->next) return head;
      ListNode *slow = head, *fast = head;
      int len = 0;
      while (slow) {
        slow = slow->next;
        ++len;
      }
      slow = head;
      ListNode node(0), *p = &node;
      ListNode* tmp;
      for (int step = 1; step <= len; step *= 2) {
        slow = fast = head;
        ListNode *s_end, *f_end;
        p = &node;
        while (slow && fast) {
          fast = slow;
          for (int j = 0; j < step && fast; ++j) {
            fast = fast->next;
          }
          s_end = f_end = fast;
          for (int j = 0; j < step && f_end; ++j) {
            f_end = f_end->next;
          }
          while (slow != s_end && fast != f_end) {
            if (slow->val < fast->val) {
              p->next = slow;
              p = p->next;
              slow = slow->next;
            } else {
              p->next = fast;
              p = p->next;
              fast = fast->next;
            }
          }
          while (slow != s_end) {
            p->next = slow;
            p = p->next;
            slow = slow->next;
          }
          while (fast != f_end) {
            p->next = fast;
            p = p->next;
            fast = fast->next;
          }
          p->next = f_end;
          slow = f_end;
        }
      }
      return node.next;
    }

    ListNode* sortList(ListNode* head) {
      return mergeSort(head);
    }
};

数组中的第K个最大元素

LeetCode中文

LeetCode英文

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

解答

方法1:堆

维护一个最小堆min，将nums前k个元素nums[i](0 <= i < k )放入min中，然后遍历第k个元素之后的元素nums[i](k <= i <= len)，比较nums[i]和堆顶元素tmp：

  1. 如果nums[i] > tmp，则从堆中弹出堆顶元素tmp，同时将num[i]放入堆中；
  2. 否则，跳过

最终，遍历完nums所有元素之后，堆顶元素即为数组nums的第k个最大元素。

  • 时间复杂度：O(n log k)
  • 空间复杂度：O(k)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        if(k <= 0 || len == 0 || len < k)
            return 0;
        
        vector<int> min(nums.begin(),nums.begin()+k);
        make_heap(min.begin(),min.end(),greater<int>());
        
        for(int i=k;i<len;i++)
        {
            int tmp = min.front();
            if(nums[i] > tmp)
            {
                pop_heap(min.begin(),min.end(),greater<int>());
                min.pop_back();
                
                min.push_back(nums[i]);
                push_heap(min.begin(),min.end(),greater<int>());
            }
        }
        
        return min[0];
    }
};

方法2：红黑树

利用红黑树自动排序的功能，思路和堆的解法类似，利用STL的multiset结构(底层红黑树实现),排序方式定义为less<int>(从小到大)，最终遍历完nums元素之后，红黑树的第一个元素即为数组第k个最大元素。

  • 时间复杂度：O(n log k)
  • 空间复杂度：O(k)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        if(k <= 0 || len == 0 || len < k)
            return 0;
        
        //红黑树实现
        multiset<int,less<int>> st(nums.begin(),nums.begin()+k,less<int>());
        
        for(auto it = nums.begin() + k;it != nums.end();it++)
        {
            auto iter = st.begin();
            if(*iter < *it)
            {
                st.erase(iter);
                st.insert(*it);
            }
        }
        
        return *(st.begin());
    }
};

方法3：快排

利用快速排序中的partition功能,partition根据所选的主元pivot，将数组分为三段：左半段 < pivot,中间段 = pivot,右半段 > pivot，设= pivot段的左边缘为l，右边缘为r，维护两个指针start和end确定第k大元素所在区间，同时初始化start = 0，end = len-1，然后partition每处理一次，就比较k-1和l大小以及k-1和r大小，处理情况如下：

  1. 如果l > k-1，则第k个最大元素位于< pivot段，令end = l；
  2. 如果r < k-1，则第k个最大元素位于> pivot段，令start = r；
  3. 如果l <= k-1 <= r，则找到了第k个最大元素，返回nums[k-1]。

假设每次partition处理后，左半段和右半段都被分为对等的两段，此时时间复杂度最优为O(n)，而最坏时间复杂度为O(n2)

  • 时间复杂度：O(n)~O(n2)
  • 空间复杂度：O(1)
class Solution {
public:
    pair<int,int> partition(vector<int>& vec,int l,int r)
    {
        int m = l + (r -l)/2;
        if(vec[l] > vec[r])
            swap(vec[l],vec[r]);
        if(vec[l] > vec[m])
            swap(vec[l],vec[m]);
        if(vec[m] > vec[r])
            swap(vec[m],vec[r]);
        
        swap(vec[l],vec[m]);
        int pivot = vec[l];
        int len = vec.size();
        int more = l;
        int cur = l+1;
        int less = r+1;
       
        while(cur < less)
        {
            if(vec[cur] > pivot)
            {
                swap(vec[++more],vec[cur++]);
            }
            else if(vec[cur] < pivot)
            {
                swap(vec[--less],vec[cur]);
            }
            else
                cur++;
        }
        
        swap(vec[l],vec[more]);
        more--;
        
        return make_pair(more+1,less-1);
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        //快排partition实现
        int len=nums.size();
        if(k <= 0 || len == 0 || len < k)
            return 0;
        
       pair<int,int> pr = partition(nums,0,len-1);
        
	   int start = 0;
	   int end = len - 1;
        while(k-1 < pr.first || k-1 > pr.second)
        {
            if(k-1 < pr.first)
			{
				end = pr.first - 1;
                pr = partition(nums,start,end);
			}
            else if(k-1 > pr.second)
			{
				start = pr.second + 1;
                pr = partition(nums,start,end);
			}
        }
        
        return nums[k-1];
    }
};

前K个高频元素

LeetCode中文

LeetCode英文

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

说明：

  • 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
  • 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

解答

方法1：哈希表 + 堆/红黑树

首先利用哈希表统计数组每个元素出现的次数，然后问题转化为 数组中的第K个最大元素 的 方法1 和 方法2。

  • 时间复杂度：O(n log k)
  • 空间复杂度：O(k)

方法2：哈希表 + 快排

首先利用哈希表统计数组每个元素出现的次数，然后问题转化为 数组中的第K个最大元素 的 方法3。

  • 时间复杂度：O(n)~O(n2)
  • 空间复杂度：O(1)

方法3：桶排序

利用桶排序中的计数排序。首先用哈希表统计每个元素的频率，然后创建桶数组bucket，bucket长度为nums.size() + 1，数组下标表示元素的频率，每个桶也是一个数组，内含出现频率等于相应下标i的元素。例如bucket[i]表示出现频率为i的桶，内含所有出现i次的元素。最后，按频率从高到低输出k个数字到结果中。

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        for(auto a : nums)
            mp[a]++;
        
        vector<int> res;
        int len = nums.size();
        vector<vector<int>> buckets(len+1,vector<int>());
        
        for(auto a : mp)
        {
            buckets[a.second].push_back(a.first);
        }
        
        for(int i=len;i>=0;i--)
        {
            for(auto b : buckets[i])
            {
                res.push_back(b);
                k--;
                
                if(k == 0)
                    return res;
            }
        }
        
        return vector<int>();
    }
};

最大间距

LeetCode中文

LeetCode英文

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

示例 1:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

说明:

  • 你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
  • 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

解答

利用基数排序。首先取桶的个数为nums.size()+1，然后遍历一遍数组找出元素最大值Max和最小值Min，将Min放入第一个桶，Max放入最后一个桶，整个大范围 Max~Min 被平分成多个局部范围，每个桶对应一个局部范围，数组的每个元素都一定位于某一个桶当中，而且由于桶的个数比数组长度大1，那么就一定存在一个空桶，由于第一个桶和最后一个桶都装有元素，所以在这个空桶前面和后面一定都能找到一个最近的非空桶，又因为每个桶的范围大小一样，那么数组排序后最大间距的相邻元素一定不位于同一个桶中，而是一个非空桶的局部最小值和它前一个非空桶的局部最大值之间的差值。因此，找到每个非空桶的局部最小值和局部最大值，找出相邻非空桶局部最小值和局部最大值的最大差值即可。

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
class Solution {
public:
    unsigned int getpos(int max,int min,int len,int num)
    {
        double a = num - min;
	    double b = max - min;
	
	    return (unsigned int)(a * len / b);
    }
    
    int maximumGap(vector<int>& nums) {
        int len = nums.size();
        if(len <= 1) return 0;
        
        vector<bool> flag(len + 1,false);
        vector<int> maxs(len + 1,INT_MIN);
        vector<int> mins(len + 1,INT_MAX);
        int Max = INT_MIN;
        int Min = INT_MAX;
        
        for(int i=0;i<len;i++)
        {
            Min = min(nums[i],Min);
            Max = max(nums[i],Max);
        }
        
        if(Min == Max) return 0;
        
        flag[0] = true;
        flag[len] = true;
        
        for(int i=0;i<len;i++)
        {
            unsigned int pos = getpos(Max,Min,len,nums[i]);
            mins[pos] = min(mins[pos],nums[i]);
            maxs[pos] = max(maxs[pos],nums[i]);
            flag[pos] = true;
        }
        
        int res = INT_MIN;
        bool flag1 = false;
        int lastMax = maxs[0];
        for(int i=1;i<=len;i++)
        {
            if(flag[i])
            {
                res = max(res,mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        
        return res;
    }
};