题目  已知一个数组中存在一个众数，请找出这个众数。众数是指一个数组中的数出现的次数超过数组长度的一半。思路  看到这道题的第一眼，想到的方法是，遍历数组，给每个数计数，然后找到数量最多的数返回。这个算法的时间和空间复杂度都是O(n)。没想到还有更优秀的做法。这个方法就是摩尔投票法。摩尔投票法的思路就是，遍历数组，也是给数计数，不过有点不一样。  首先任选一个候选人，计数为1，一般都是从第一个数开始。遇到相同的数就加1，遇到不同的就减1，如果计数为0，则把当前的数作为候选人，计数为1。重复这个过程到数组的最后。候选人就是答案。时间复杂度为O(n),空间复杂度为O(1)代码class Solution { public: int majorityElement(vector<int>& nums) { int count = 1; int maj = nums[0]; for(int i = 1;i < nums.size();i++) {

一、定义： 所有的父节点都小于子节点的完全二叉树。叫做小根堆。二、性质：节点个数为N的小根堆，其高度为logN。N/2之后的节点都是叶子结点。第i个节点的左儿子的序号是ix2,右儿子的序号是ix2+1，父亲节点的序号为i/2三、如何存储? 用一维数组存储。申请一个长度为N+1的数组，四、建堆的两种方式：直接用一个数组存储数，然后，从后往前依次调整数的位置，使以当前位置为根的二叉树为小根堆直到数组的第一个数。插入法，依次读入每个数，把它插入小根堆，并调整位置，使插入数后二叉树继续保持为小根堆方式一代码 文末代码中create1方法 方式二代码 文末代码中create2方法五、排序时间复杂度为 NlogN 文末代码中heapSort方法六、从堆顶删除一个数? 文末代码中deleteMin方法七、增加一个数? 文末代码中addOneNum方法class SmallPriorityQueue { vector<int> h; int N; public: SmallPriorityQueue(vector<int> & arr,

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。leetcode原题：https://leetcode.cn/problems/sliding-window-maximum思路:直观思路就是暴力，暴力是万能的。每向右滑动一下，都有k个数，遍历这k个数，可以得到一个最大值。维持k个数的最大值，还有一个方法也很直观，就是使用优先队列，即大根堆。时空复杂度更好的就是使用双端队列，让队列里的数，时刻保持单调递减。这样每次取最大值的时候直接使用队列头部的数即可。使用双端队列的时候，入队的是什么也很重要，一开始想的是入数组里的数，发现窗口左端右移的时候不好判断。而把下标入队，就非常容易了。代码：vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> ans; deque<int> window; for

给定一个由 0 和 1 组成的数组 arr ，将数组分成  3 个非空的部分 ，使得所有这些部分表示相同的二进制值。如果可以做到，请返回任何 [i, j]，其中 i+1 < j，这样一来：arr[0], arr[1], ..., arr[i] 为第一部分；arr[i + 1], arr[i + 2], ..., arr[j - 1] 为第二部分；arr[j], arr[j + 1], ..., arr[arr.length - 1] 为第三部分。这三个部分所表示的二进制值相等。如果无法做到，就返回 [-1, -1]。注意，在考虑每个部分所表示的二进制时，应当将其看作一个整体。例如，[1,1,0] 表示十进制中的 6，而不会是 3。此外，前导零也是被允许的，所以 [0,1,1] 和 [1,1] 表示相同的值。示例 1：输入：arr = [1,0,1,0,1]输出：[0,3]示例 2：输入：arr = [1,1,0,1,1]输出：[-1,-1]示例 3:输入：arr = [1,1,0,0,1]输出：[0,2]本题是leetcode原题思路：分成三段后，是什么样子的?三部分中，每个部分