Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

Posted on Edited on In Valine:

选择问题

从n个元素的集合中选择第i个顺序统计量的问题形式化地归结为“选择问题”。

中位数和顺序统计量

1）顺序统计量：在一个由n个元素组成的集合中，第i个顺序统计量(order statistic)是该集合中的第i小的元素。如：在一个元素集合中，最小值是第1个顺序统计量（i=1）；最大值是第n个顺序统计量（i=n）

2）中位数：对一个有n个元素的集合，将数据排序后，位置在最中间的数称为该集合的中位数。

最大值最小值

针对一个序列取得最大和最小值均需要n-1次比较。这是一个下限，确定最大值或者最小值的算法可以看作各个元素之间一场锦标赛，每次比较都是一场比赛，两个元素中较小的或者较大的获胜，除了最终的最大值和最小值，所有其他元素都需要输一次，所以n-1次是必须的。

接下来是一些比较有意思的问题，比如同时找出最小值和最大值，当然可以n-1次比较找出最大值，然后n-2次比较找出最小值，不过还是有比这个更好一点的算法，把元素两两分组，然后比较产生一个较大的值和较小的值，然后较大的值中产生最大值，较小的值中产生最小值，此时需要比较操作的次数至多3|_n/2_|。

最大与次大问题

还有一个比较问题是同时找出最大、第二大或者最次小元素的比较次数，简单的当然是2n-3，不过也有一个分组的方法能够达到$n+lgn-2$的比较次数。比较方法如下：

上面已经说明了，找出最值最少的比较次数n-1，所以上面寻找的方法也是n-1次，不信可以累计求和，不过这样求最值的过程中最值上来的时候有一条路径被记录，这条路径的长度为lgn，找出次大值或者次小值直接在这个路径上寻找就只需要lgn-1的比较次数。(但是这种算法不适用于存在重复元素的情况)

原理：锦标赛算法，分组，两两比较；次大值一定跟最大值PK过。

Posted on Edited on In Valine:

Maximum and minimum of an array using minimum number of comparisons
Write a C function to return minimum and maximum in an array. You program should make minimum number of comparisons.

解答思路：

法1: Pair Compare
目标：尽可能的减少比较，如何确定a[i]是不是最小值或者最大值呢？

基于比较，消除不确定性
a[i]跟a[i+1] 比较之后？
a[i] 如果比 a[i+1] 则a[i]才有可能跟max比较；a[i+1] 才有可能跟min比较；

结论：3次比较消除了2个元素的的不确定性；

a[i]跟min, max比较；
a[i+1]跟min, max比较；
结论：4次比较，完成了2个元素的确定性；

法2: Divide and Conquer
如果有两个元素？ 怎么选择最大值最小值？
如果有一个元素，怎么选择最大值最小值？
左半部分已经有了最大值，最小值；右半部分已经有了最小值最大值： 如何确定merge之后的最小值最大值？

Posted on Edited on In Valine:

输入n个整数，找出其中最小的k个数。

注意：

数据保证k一定小于等于输入数组的长度;
输出数组内元素请按从小到大顺序排序;
样例
输入：[1,2,3,4,5,6,7,8] , k=4

输出：[1,2,3,4]

常见解法：

  • 排序
  • 借助堆: 借助大小为K的堆，从而实现快速比较。
  • 线性选择（快排思想） —普通：最坏的时间复杂度$O(lgn)$
  • 线性选择（快排思想） —基于中位数的select升级：借助基于中位数的select算法来选择枢点，可以尽可能的2分问题，从而使得最坏的时间复杂度控制在$O(n)$
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
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int, vector<int>, less<int>> q; //大顶堆
        
        for (int i = 0; i < input.size(); ++i) {
            if (q.size() < k) {
                q.push(input[i]);
            }
            else {
                if (input[i] < q.top()) {
                    q.pop();
                    q.push(input[i]);
                }
            }
        }
        
        vector<int> res;
        
        while (q.size()) {
            res.push_back(q.top());
            q.pop();
        }
        
        reverse(res.begin(), res.end());
        return res;
    }
};

Posted on Edited on In , Valine:

https://www.jianshu.com/p/45f4c5f74c8e

问题：

最大间隙问题。给定 n 个实数，求这n个实数在数轴上相邻2个数之间的最大差值，设计解最大间隙问题的线性时间算法。

分析：

该问题最先想到可能就是排序后计算，但排序的时间复杂度最少为O(nlongn)，不能满足题意的线性时间算法。

所以有一个解决该问题的算法，筒排序。

该算法的思想为，将n个数的最大值、最小值找到，在[ min ,max ]区间内，分成n-1个等大的区间，每个区间的大小为

len = （max - min）/（n-1），然后将n个数字填入到这n-1个区间中，并根据填入的数，找到该区间内数字的最大值与最小值。除去两边的最大值和最小值，只需要将n-2 个数字填入到 n-1个区间中，根据抽屉原理，那至少有一个空的区间，所以，最大间隙一定产生在两个不同区间之间。

为什么从$O(nlgn)$可以优化到$O(n)$?

对数据进行处理之后，在对处理之后的序列进行相关操作，这是一种很常见的解决问题的思路。

其中，第一步的处理包括：排序、对数据合理的分组等; 借助第一步的预处理，然后再根据一些数学特性去排除一些肯定不可能成为答案的解，从而提到算法效率。

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
40
41
42
43
44
45
46
47
48
49
const int N = 100010;
struct Bucket {
    bool used;
    int minv;
    int maxv;
} buckets [N];



class Solution {
public:

    int maximumGap(vector<int>& nums) {
        memset(buckets, 0, sizeof(buckets));
        if (nums.size() < 2) return 0;
        //桶排序 + 鸽巢原理
        int minv = 0x3f3f3f3f, maxv = 0, n = nums.size();
        for (auto x : nums) {
            if (x <= minv)  minv = x;
            if (x >= maxv) maxv = x;
        }

        int gap = max(1, (maxv - minv) / (n - 1));
        int gap_cnt = (maxv -minv) / gap + 1;

        for (auto x : nums) {
            int i = (x - minv) / gap;
            cout << i  << " "<< x << " "<< gap<< endl;

            if (!buckets[i].used) {
                buckets[i].used = true;
                buckets[i].minv = 0x3f3f3f3f;
                buckets[i].maxv = 0;
            }
            buckets[i].minv = min(buckets[i].minv, x);
            buckets[i].maxv = max(buckets[i].maxv, x);
        }  

        int res = 0;
        int pre = minv;
        for (int i = 0; i < gap_cnt; ++i) {
            if (!buckets[i].used) continue;
            res = max(buckets[i].minv - pre, res);
            pre = buckets[i].maxv;
        }

        return res;
    }
};

Posted on Edited on In , Valine:

在字符串中找出第一个只出现一次的字符。

如输入”abaccdeff”，则输出b。

如果字符串中不存在只出现一次的字符，返回#字符。

样例：
输入：”abaccdeff”

输出：’b’

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    char firstNotRepeatingChar(string s) {
        map<char, int> counter;
        for (auto x: s) {
            counter[x]++;
        }
        for (auto x: s) {
            if (counter[x] == 1) {
                return x;
            }
        }

        return '#';
    }
};

请实现一个函数用来找出字符流中第一个只出现一次的字符。

例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是’g’。

当从该字符流中读出前六个字符”google”时，第一个只出现一次的字符是’l’。

如果当前字符流没有存在出现一次的字符，返回#字符。

样例
输入：”gabcdgle”

输出：”ggg#ll”

解释：每当字符流读入一个字符，就进行一次判断并输出当前的第一个只出现一次的字符。

解题思路：

第一个只出现一次，表示顺序，需要有队列。 谁，什么时候入队列？什么时候出队列？
通过map记录次数

goo

Posted on Edited on In , Valine:

子数组最大和—题目描述

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例
输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

子数组最大和—思路

子数组的最大值，这是一个求最值问题，十有八九使用动态规划。【这个是我们的经验-求最值问题，十有八九使用动态规划】

拿到一个问题，我们首先要去思考他的解空间有多大？又或者说，计算机用最笨的方法去枚举的话，最多需要枚举多少次。

所有的子数组和的最大值，我需要枚举start, end, 解空间有$n^2$

接着我们再来回答我们接下来要做什么？ 我们需要去检查这一组解是否是最优解。
如何判断呢？ 这个是一个判定问题。

对这个题目而言，我们的解决步骤如下：
从start到end累加得到一个数，累加的时间复杂度是$O(N)$

最终的时间复杂度是$O(n^3)$

动态规划思路

一维最大子数组和 最大子数组和系列
问题描述 给定一个整数数组 nums 计作$A_i$，找到一个具有最大和的子数组（子数组最少包含一个元素），返回其最大和
状态表示 F[i]表示利用以$A_i$结尾的子数组的最大和
转移方程 $F[i]=\begin{cases}F[i-1]+A[i] & \text{if } F[i-1] \gt 0 \\ A[i] & \text{if } F[i-1] \le 0 \end{cases}$
边界 F[0]=0
目标 F[N]
空间压缩 由于仅与前一项有关，所以可以用一个变量来代替

子数组最大和—代码

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
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        /*
        dp[i] = num[i] if dp[i - 1] < 0; 
        dp[i] = dp[i - 1] + num[i]; if dp[i - 1] >= 0
        表示以A[i]结尾的子数组的子数组最大和。
        最终的结果，一定是dp[i]中选择一个最大的。
        */
        
        int sum = 0;
        int res = INT_MIN;
        for (int i = 0; i < nums.size(); ++i) {
            if (sum < 0) {
                sum = nums[i];
            }
            else {
                sum += nums[i];
            }
            
            res = max(res, sum);
        }
        
        return res;
    }
};

Posted on Edited on In , Valine:

题目描述

如何得到一个数据流中的中位数？

如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。

如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

样例
输入：1, 2, 3, 4

输出：1,1.5,2,2.5

解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。

思路

算法实现时，一个蛮重要的点在每次都要往某一个某一个堆中添加元素（即使不应该插入，也要先插入另一个，再移动元素过去）。

按照刚才提到的步骤来操作，可以大幅减少过多的分支判断，让你的思路更加清晰。

代码

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
class Solution {
public:
    priority_queue<int, vector<int>, less<int>> sh; //大根堆，存最小的一半
    priority_queue<int, vector<int>, greater<int>> bh;//小根对，存最大的一半
    
    void insert(int num){
        //总会向大的一半中新增一个。
        if (bh.empty() || num > bh.top()) {
            bh.push(num);
        }
        else { 
            sh.push(num);
            bh.push(sh.top());
            sh.pop();
        }
        
        //如果已经失调，则进行调整
        if (bh.size() == sh.size() + 2) {
            sh.push(bh.top());
            bh.pop();
        }
    }

    double getMedian(){
        if ((bh.size() + sh.size()) & 1) {
            return bh.top();
        }
        else {
            return (bh.top() + sh.top()) / 2.0;
        }
    }
};

Posted on Edited on In Valine:

扫描线是一条想象中的向右扫过平面的竖直线。也因此，以此思想为基础的算法也被称为平面扫描算法(Plane Sweep Algorithm)，我们以某些事件为基础扫描我们思考的问题以使扫描离散化。

这些事件都是以我们思考的问题为基础，我们将在下面讨论的算法中看见。除去这些事件以外，我们需要维护一些数据结构来储存以y坐标为顺序排列的点（这一顺序有时可能会改变）以助益于在扫描到某些事件时进行操作。在一些情况，该数据结构只储存活动事件。

另一个需要注意的事情是，这种算法的效率取决于我们选用的数据结构。一般地，我们可以用C++中的set，但有时可能我们需要储存更多东西，所以我们可能采用平衡二叉树。

Posted on Edited on In Valine:

一类是「快慢指针」，另一类是「左右指针」

前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分查找。

双指针类 （数组A，2*n个元素，n个奇数、n个偶数，设计一个算法，使得数组奇数下标位置放置的都是奇数，偶数下标位置放置的都是偶数 两种思路：双指针、借助于栈）

盛水做多的容器

Read more »

Posted on Edited on In , Valine:

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组，求出这个数组中的逆序对的总数。

样例
输入：[1,2,3,4,5,6,0]

输出：6

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    vector<int> nums;
    vector<int> cp;
    int cnt;

    void merge(int l, int m, int r) {
        int k = l;
        while (k <= r) {
            cp[k] = nums[k];
            k++;
        }

        int i = l;
        int j = m + 1;
        k = l;

        while (i <= m && j <= r) {
            if (cp[i] <= cp[j]) 
            {
                nums[k++] = cp[i++];
            }
            else {
                cnt += (m - i + 1);
                nums[k++] = cp[j++];
            }
        }

        while (i <= m) {
            nums[k++] = cp[i++];
        }
        while (j <= r) {
            nums[k++] = cp[j++];
        }
    }

    void dfs(int l, int r) {
        if (l == r) return;
        int mid = l + r >> 1;
        dfs(l, mid);
        dfs(mid + 1, r);
        merge(l, mid, r);
    }

    int inversePairs(vector<int>& _nums) {
        if (_nums.empty()) return 0;
        nums = _nums;
        cnt = 0;
        cp.resize(nums.size());
        dfs(0, nums.size() - 1);
        return cnt;
    }
};