连续子数组的最大和
连续子数组的最大和_牛客题霸_牛客网
描述
输入一个长度为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;
}
};
