打印N个数组中整体最大的topK

一、题目

有N 个长度不一的数组，所有的数组都是有序的，请从大到小打印这N 个数组整体最大的前K 个数。

例如：

1
2
3
4
5
6

输入含有 N 行元素的二维数组可以代表N个一维数组
{219, 405, 538, 845, 971},
{148, 558},
{52, 99, 348, 691},
再输入整数 K = 5，打印：
top 5: 971， 845， 691， 558， 538

二、思路

topK 问题统一使用堆来解决适合大部分场景。此题目也是使用堆来解决。题目的前提条件是数组是有序的。

一、题目

二、分析

使用一个 set 直接保存数组中元素，这种做法的空间复杂度为 O(n)，不符合我们优化解。

我们使用下标去做运算，会修改数组内容。就是当前数字对应那个下标，把下标内容数据变成nums[i] - n 为负数，然后判定是不是为负数就行了。

1

找到无序数组中最小的K个数

一、题目

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

Leetocde：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/

二、思路

无序数组中找最小的、或者最大的 K 个数，这种题目一般排序的思路是不符合要求的，排序的时间复杂度达到了 O(n*logn)，而我们可以选择堆这种数据结构来做。可以让时间复杂度为 O(nlogK)

如果求最小的 K 个数，那么就需要维护一个大根堆。否则应该维护一个小根堆。先申请一个 K 长度的数组，然后往数组中插入 K 个数字，使其满足大根堆。然后依次插入数组中剩下的元素到大根堆中，如果发现元素小于堆顶元素，就给他插入堆中，并调节堆。

遍历完成，大根堆中的元素即为无序数组中最小的 K 个数

一、题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

1
2

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

Leetcode：https://leetcode.cn/problems/kth-largest-element-in-an-array/

一、题目

给定一个数字字符串S和一个数组nums，数组中的元素都在0~9之间，问从数组中选择元素组成的数字，小于N的最大值是多少？

例如 A={1, 2, 4, 9}，x=2533，返回 2499

二、分析

如下是我们的思路

1. 拿到原始字符串 S 和数组 nums 后，首先看能否拼出和 S 长度一样的字符串吗？

我们先将数组 nums 中的元素进行排序（从小到大），然后拿到数组 nums 中最小的数字，得到 min_val，与字符串 S 的第一位对比

本文来介绍下外部排序

一、归并形式的外部排序

由两个阶段构成：

• 按照给定的内存大小，将大文件分成若干个小文件，这个小文件容量应该小于内存的可使用容量。然后将各个小文件依次读入内存，然后使用适当的内部排序算法对其进行排序，排好序之后写入对应的小文件。此时，我们就可以获得若干个排好序的小文件。
• 然后对若干个小文件进行两两归并，直到得到一个完整的有序文件。

经典的快速排序，先上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) {
            return nums;
        }
        srand(time(nullptr));
        sort_array_sub(nums, 0, nums.size()-1);
        return nums;
    }

private:
    void sort_array_sub(std::vector<int>& nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int pos = rand() % (right-left+1) + left;
        std::swap(nums[pos], nums[left]);
        int pivot = nums[left];
        int less = left;
        int more = right+1;
        int j = left+1;
        while (j < more) {
            if (nums[j] < pivot) {
                less++;
                std::swap(nums[less], nums[j]);
                j++;
            } else if (nums[j] == pivot) {
                j++;
            } else {
                more--;
                std::swap(nums[j], nums[more]);
            }
        }
        std::swap(nums[less], nums[left]);
        sort_array_sub(nums, left, less-1);
        sort_array_sub(nums, more, right);
    }
};

我们随机去拿到一个 pivot 点，然后将其放在当前区间的最左边。最左边记为 left，然后我们从 left+1 位置开始遍历，到 right 位置结束。

我们的这个区间可以分为三份，左边部分全部是小于 pivot 的，中间部分全是等于 pivot 的，右边部分全是大于 pivot 的。三个区间分为：[left, less-1], [less, more-1], [more, right]

一、题目

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

1
2
3

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

一、题目

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

Leetcode：https://leetcode.cn/problems/n-queens/

Leetcode：https://leetcode.cn/problems/n-queens-ii/

二、分析

如果在 (i, j) 位置放置了一个皇后，然后

一、题目

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

Leetcode：https://leetcode.cn/problems/next-permutation