嵌入式之数据结构篇（五）

五、数据结构与算法

程序 = 数据结构 + 算法

1.数组

数组是存放在连续空间上的相同类型数据集合

• 数组下标是从0开始的
• 数组内存空间地址是连续的

二分查找：给定一个n个元素升序的整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。

提示：

• 你可以假设nums中所有元素是不重复的
• n将在[1，10000]之间
• nums的每个元素都将在[-9999,9999]之间

// 左闭右闭区间内二分查找
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) { // 注意边界条件
            int middle = left + (right - left) / 2; // 防止变量值溢出
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) left = middle + 1;
            else return middle;
        }
        return -1; // 未找到目标值
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析：

• 时间复杂度：O(logN)
• 空间复杂度：O(1)

2.链表

链表是一种通过指针串联在一起的线性结构，每一个结点有两部分组成，一个是指针域，一个是数据域，每个指针域存放指向下一个节点的指针，最后一个结点指针域指向空指针。

链表在内存中不是连续分布的，这一点区别于数组。

反转链表：反转一个单链表，例如输入：1->2->3->nullptr，输出：3->2->1->nullptr

// 双指针法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 用来存放cur的下一个结点
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while (cur) {
            temp = cur->next;
            cur->next = pre; // 翻转
            // 更新cur和pre，继续移动
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

3.哈希表

哈希表（Hash table），也成为散列表，与数组相比较的话其实是带上索引的数组，存在键值对，键Key，值Value，例如在学校中，学号作为键，姓名作为值，通过学号可以找到对应名字的人。

两数之和：给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以建设每种输入只会对应一个答案，但是数组中同一个元素不能使用两遍。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // key是元素值，value是对应元素下标
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            // 遍历当前元素，并在map中查找是否有对应的key
            auto iter = map.find(target - nums[i]);
            if (iter != map.end()) {
                return {iter->second, i};
            }
            map.insert(pair<int, int> (nums[i], i));
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析：

• 时间复杂度：O(N)
• 空间复杂度：O(N)

4.栈与队列

栈（stack）是先进后出，队列（queue）是先进先出，还有一种双端队列（deque）

滑动窗口最大值：给定一个数组nums，有一个大小为k的滑动窗口从数组的最左端移动到最右端，你只可以看到滑动窗口内的k个数字，滑动窗口每次只能向右移动一位。

进阶：你能在线性时间复杂度内解决此题吗？

// 利用单调队列，每次最大元素都在前端，后端进入的元素按照从大到小排列
class Solution {
private:
    class MyQueue { 
    public:
        deque<int> deq; // 双端队列，弹出的时候与队列出口元素进行比较
        void pop(int value) {
            if (!dep.empty() && value == dep.front()) {
                dep.pop_front();
            }
        }
        void push(int value) {
            while (!dep.empty() && value > deq.back()) {
                deq.pop_back();
            }
            dep.push_back(value);
        }
        int front() {
            return dep.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue dep;
        vector<int> res;
        for (int i = 0; i < k; i++) {
            dep.push(nums[i]);
        }
        res.push_back(dep.front()); // 记录了当前最大值
        for (int i = k; i < nums.size(); i++) {
            // 移除之前元素，加入后来元素
            dep.pop(nums[i - k]);
            dep.push(nums[i]);
            res.push_back(dep.front());
        }
        return res;
    }
};
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

复杂度分析：

• 时间复杂度：O(N)
• 空间复杂度：O(M)，M为定义的辅助队列所占用的空间大小

5.二叉树

二叉树是n个结点的有限集，或者是空集，或者由一个根节点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树构成。（二叉树结构简单，规律性强）

特点：1、每个结点最多有两孩子；2、子树有左右之分，其次序不能颠倒；3、二叉树可以是空集合，根可以有空的左子树或者是空的右子树。

二叉树的前序遍历：

// 递归方法，中左右
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == nullptr) return;
        vec.push_back(cur->val); // 对中的操作
        traversal(cur->left, vec); // 递归左结点
        traversal(cur->right, vec); // 递归右结点
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root, res);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析：

• 时间复杂度：O(N)
• 空间复杂度：O(N)

6.查找算法

1、顺序查找，即进行遍历操作并逐个比较，若相等则查找成功，否则查找失败

2、二分查找，设置中间值middle进行比较，小于middle时在左半部分查找，大于middle时在右半部分查找

3、插值查找，基于二分查找算法，将查找点的选择改为自适应选择，可以提高查找效率

4、斐波那契查找，二分查找的改进，引入斐波那契数组进行查找

5、树表查找，对二叉树进行中序遍历，可以得到有序的数列

6、分块查找，将元素分为有序的多块，块中元素可以无序，但是块与块之间必须有序

7、哈希查找，数组下标和元素形成对应关系

7.排序算法

1、冒泡排序：从前往后依次比较前后两个相邻元素，将大的置于右端，小的置于左端，依次比较，时间复杂度：O(N²)

2、选择排序：每次从需要排序序列中选择一个最小值放于序列最左端，时间复杂度：O(N²)

3、插入排序：依次插入到排好序的子序列中，时间复杂度：O(N²)

4、希尔排序：将排序序列中相隔某个增量的记录组成一个子表，对各个子表分别进行插入排序，最后再进行一次直接插入排序，时间复杂度：O(N²)

5、归并排序：将两个或者两个以上的有序表组合成一个新的有序表，时间复杂度：O(NlogN)

6、快速排序：选择枢轴元素pivot，一边排序后分割成两部分，前一部分小于pivot，后一部分大于pivot，针对这两部分重复上述操作，时间复杂度：O(N²)

7、堆排序：把N个元素建成大顶堆，输出最大元素后进行堆调整，时间复杂度：O(NlogN)