Neo's Blog

第k大元素

Posted on 2021-01-02 Edited on 2024-12-09 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)$

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;//注意这里要加const，下面才可以定义全局变量q[]
int q[N];
 
int quick_choose(int l, int r, int k){
    if(l==r) return q[l];//区间里只有一个数
    
    int i = l-1, j = r+1, x = q[(l+r)/2];
    while(i<j){
     while(q[++i]<x);
     while(q[--j]>x);  
     if(i<j){
         swap(q[i], q[j]);
     }
    }
    //
    int sl = j-l+1;//左区间多少数
    if(k<=sl) return quick_choose(l,j,k);
    if(k>sl) return quick_choose(j+1,r,k-sl);
}
 
int main(){
    int n,k;
    cin >> n >> k;
    for(int i=0; i<n; i++){
        cin >> q[i];
    }
    cout << quick_choose(0,n-1,k) << endl;
    
}

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 2020-12-30 Edited on 2022-03-02 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)$?

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

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

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 2020-12-29 Edited on 2022-10-29 In 数据结构与算法 , 剑指Offer Valine:

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

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

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

样例：
输入：”abaccdeff”

输出：’b’

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 2020-12-29 Edited on 2022-03-03 In 数据结构与算法 , 剑指Offer 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]
空间压缩	由于仅与前一项有关，所以可以用一个变量来代替

子数组最大和—代码

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 2020-12-29 Edited on 2024-12-16 In 数据结构与算法 , 剑指Offer Valine:

题目描述

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

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

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

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

输出：1,1.5,2,2.5

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

思路

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

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

代码

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 2020-12-29 Edited on 2022-03-02 In 数据结构与算法 Valine:

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

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

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

双指针技巧

Posted on 2020-12-29 Edited on 2022-03-02 In 数据结构与算法 Valine:

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

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

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

盛水做多的容器

逆序数计算系列

Posted on 2020-12-29 Edited on 2022-03-03 In 数据结构与算法 , 剑指Offer Valine:

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

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

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

输出：6

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;
    }
};

链表第一个公共节点

Posted on 2020-12-29 Edited on 2022-03-01 In 数据结构与算法 , 剑指Offer Valine:

输入两个链表，找出它们的第一个公共结点。

当不存在公共节点时，返回空节点。

样例
给出两个链表如下所示：
A： a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3

输出第一个公共节点c1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *h1, ListNode *h2) {
        int c1 = 0, c2 = 0;
       for (auto p = h1; p; p = p->next) c1++;
       for (auto p = h2; p; p = p->next) c2++;
       
       auto p1 = h1;
       auto p2 = h2;
        while (c2 < c1) {
            p1 = h1 = h1->next;
            c2++;
        }
        while (c1 < c2) {
            p2 = h2 = h2->next;
            c1++;
        }

       while (p1 && p2 && p1 != p2) {
           p1 = p1->next;
           p2 = p2->next;
       }

       return p1;
    }
};

数据结构与算法-概览

Posted on 2020-12-28 Edited on 2022-03-04 Valine:

建立秩序，省却搜索。—德国谚语

计算机解决问题，就靠搜索。而通过建立秩序，可以让计算机更聪明的完成搜索。

而这里的建立秩序，就包括：

为具体场景设计更合适的数据结构。这一块对应数据结构。
为具体场景设计更好的搜索策略。这一块对应算法。

两大类存储引擎：

日志结构（log-structured）的存储引擎，以及面向页面（page-oriented）的存储引擎（例如B树）。

SSTable

排序字符串表（Sorted String Table）

参考：https://vonng.gitbooks.io/ddia-cn/content/glossary.html