一个懒散的程序猿

之前总结了常见的十种排序算法,但是不做题怎么可能巩固呢?

215.第K个最大元素

这道题很关键，建议熟练掌握

思路一： 快速选择, 类似于快速排序, 不过只需要找到第 K 大的值即可, 不需要对其左右全都进行排序

int findKthLargest(vector<int>& nums, int k) {
    int len = nums.size();
    return quick_sort_recursive(nums, 0, len-1, len-k);
}

void quick_sort_recursive(vector<int>& nums, int start, int end, int k)  
{
    int mid = nums[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (nums[left] < mid && left < right)
            left++;
        while (nums[right] >= mid && left < right)
            right--;
        std::swap(nums[left], nums[right]);
    }
    if (nums[left] >= nums[end])
        std::swap(nums[left], nums[end]);
    else
        left++;

    if (left == k)
        return nums[k];
    else if( left > k)
        quick_sort_recursive(nums, start, left - 1, k);
    else
        quick_sort_recursive(nums, left + 1, end, k);
}

思路二：最大堆，每次从对顶取一个，K-1 次之后, 堆顶就是我们的结果

void maxHeapify(vector<int>& a, int i, int heapSize) {
    int l = i * 2 + 1, r = i * 2 + 2, largest = i;
    if (l < heapSize && a[l] > a[largest]) {
        largest = l;
    } 
    if (r < heapSize && a[r] > a[largest]) {
        largest = r;
    }
    if (largest != i) {
        swap(a[i], a[largest]);
        maxHeapify(a, largest, heapSize);
    }
}

void buildMaxHeap(vector<int>& a, int heapSize) {
    for (int i = heapSize / 2; i >= 0; --i) {
        maxHeapify(a, i, heapSize);
    } 
}

int findKthLargest(vector<int>& nums, int k) {
    int heapSize = nums.size();
    buildMaxHeap(nums, heapSize);
    for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
        swap(nums[0], nums[i]);
        --heapSize;
        maxHeapify(nums, 0, heapSize);
    }
    return nums[0];
}

347.前K个高频元素

策略: 先统计出现频率, 根据频率设置若干个记录对应频率的桶, 向桶中放入数据, 然后从 大桶 逐个取出元素, 直到第 k 个

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> counts;
    int max_count = 0;
    for (const int & num : nums) {
        max_count = max(max_count, ++counts[num]);
    }
    vector<vector<int>> buckets(max_count + 1);
    for (const auto &[key, value] : counts) {
        buckets[value].push_back(key);
    }
    vector<int> ans;
    for (int i = max_count; i >= 0 && ans.size() < k; --i) {
        for (const int & num : buckets[i]) {
            ans.push_back(num);
            if (ans.size() == k) {
                break;
            }
        }
    }
    return ans;
}

451.根据字符出现频率排序

第一种: 直接创建一个可以容纳所有 char 的数组, 对应 char 位置上保存出现的频率, 根据统计的频率作为快排排序的规则, 这个有点讨巧

string frequencySort(string s) {
    int counts[CHAR_MAX + 1] = {0};
    for (char c : s) ++counts[c];
    sort(s.begin(), s.end(), [&](char a, char b) {
        return counts[a] > counts[b] || (counts[a] == counts[b] && a < b);
    });
    return s;
}

第二种: 利用桶排序的思路, 先统计出现的数量, 根据出现频率建立桶, 然后结合桶的顺序关系,将值重新排序, 也就是上一题的思路

string frequencySort(string s) {
    unordered_map<char, int> counts;
    int max_count = 0;
    for (const char &i: s) {
        max_count = max(max_count, ++counts[i] );
    }

    vector<vector<char>> buckets(max_count+1);
    for (auto &[key, value] : counts) {
        buckets[value].push_back(key);
    }

    string result;
    for(int i=max_count;i>=0;--i) {
        for (auto target : buckets[i])
            result += string(i, target);
    }
    return result;
}

75.颜色分类

如果不考虑原地这个概念，可以统计每种出现的频率后，重新给输入赋值即可

void sortColors(vector<int>& nums) {
    int length = nums.size();
    vector<int> vecCount(3, 0);
    for (int i=0; i<length ;i++) {
        vecCount[nums[i]] ++;
    }

    int cnt = 0;
    for (int i=0; i<3; i++) {
        while(vecCount[i] != 0) {
            vecCount[i] --;
            nums[cnt++] = i;
        }
    }
}

单指针，对数组进行两次遍历。在第一次遍历中，我们将数组中所有的 0 交换到数组的头部。在第二次遍历中，我们将数组中所有的 1 交换到头部的 0 之后。此时所有的 2 都出现在数组的尾部

void sortColors(vector<int>& nums) {
    int n = nums.size();
    int ptr = 0;
    for (int i = 0; i < n; ++i) {
        if (nums[i] == 0) {
            swap(nums[i], nums[ptr]);
            ++ptr;
        }
    }
    for (int i = ptr; i < n; ++i) {
        if (nums[i] == 1) {
            swap(nums[i], nums[ptr]);
            ++ptr;
        }
    }
}

双指针，对数组进行一次遍历，分别记录 0 和 2 的位置
注意：不能轻易 swap(nums[i], nums[p2])， 换过去之后，新的 nums[i] 可能还要交换

void sortColors(vector<int>& nums) {
    int n = nums.size();
    int p0 = 0, p2 = n - 1;
    for (int i = 0; i <= p2; ++i) {
        if (nums[i] == 0) {
            swap(nums[i], nums[p0]);
            ++p0;
        } else if (nums[i] == 2) {
            swap(nums[i], nums[p2]);
            --p2;
            --i;
        }
    }
}

总结

查找第K个最大元素这种题感觉特别多, 需要熟练掌握
计数和桶排序也需要熟练掌握