连续子数组的最大和

连续子数组的最大和_牛客题霸_牛客网

描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

要求:时间复杂度为 O(n)，空间复杂度为 O(n)

进阶:时间复杂度为 O(n)，空间复杂度为 O(1)

示例1

输入：[1,-2,3,10,-4,7,2,-5]
返回值：18
说明：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18  

示例2

输入：[2]
返回值：2

思路

输入的数组可以分为两种情况：

举例说明下这种思路（假如返回的结果存在ret里）：

实现

Way1：时复O(n)，空复O(1)

class Solution {
public:int FindGreatestSumOfSubArray(vector<int>& array) {int ret=0,tmp=0;for(auto k:array){if(tmp+k<0){tmp=0;}else{tmp+=k;}ret=max(ret,tmp);}if(ret==0){  //说明全是负数return *max_element(array.begin(),array.end());}return ret;}
};

Way2：时复O(n)，空复O(n)

思路还是“遍历时算结果”，只不过我们用栈来保存和。只有结果比栈顶数据大，才能入栈，这样遍历完 栈顶就是最大和了。

class Solution {
public:int FindGreatestSumOfSubArray(vector<int>& array) {stack<int> st;int ret=0;for(auto k:array){ret+=k;if(ret<=0){ret=0;}else if(st.empty()||!st.empty()&&ret>st.top()){st.push(ret);}}if(st.empty()){return *max_element(array.begin(),array.end());}return st.top();}
};

反思

我一开始总想着，怎么去找到这个 子数组的起始元素，怎么去找到末尾元素。我想着，先把子数组找到，然后算加起来的和。这其实路子走歪了。

连续子数组不是重点，我们根本不需要找到它，我们的重点，应该放在最大和上！

计算机拿到这个数组，就是把它从头到尾遍历，那我要做的，就是在遍历过程中，怎么找到最大和。

所以我要模拟这个遍历、算和的过程。

数组中出现次数超过一半的数字

数组中出现次数超过一半的数字_牛客题霸_牛客网

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

要求：空间复杂度：O(1)，时间复杂度 O(n)

输入描述： 保证数组输入非空，且保证有解

示例1：

输入：[1,2,3,2,2,2,5,4,2]
返回值：2

示例2：

输入：[3,3,3,3,2,2,2]
返回值：3

示例3：

输入：[1]
返回值：1

思路

Step1. 算长度len，数组出现的次数>len/2

Step2. 统计次数

这道题要思考的点就在于，怎么在时复O(n)的情况下，统计次数？

这说明，遍历一遍数组，我就要知道当前数的次数了。因为没有额外的空间去记录每个数据的次数，所以我遍历的时候就要判断次数是否> len/2。

之前我总结了一句话“有重复，想排序！”,这道题就可以用上。

先给数组排序，把相同的放一起 便于统计。遍历时，设一个记录次数的count，遍历一遍，前后相同就用count++来计数。

实现

class Solution {
public:int MoreThanHalfNum_Solution(vector<int>& numbers) {int half=numbers.size()/2;int count=1;
​sort(numbers.begin(),numbers.end());for(int i=0;i<numbers.size();i++){if(i>0&&numbers[i]==numbers[i-1]){count++;}else{count=1;}
​if(count>half){return numbers[i];}}return 0;}
};