【vector题解】连续子数组的最大和 | 数组中出现次数超过一次的数字

连续子数组的最大和

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

描述

输入一个长度为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;isize();i++){
            if(i>0&&numbers[i]==numbers[i-1]){
                count++;
            }
            else{
                count=1;
            }
​
            if(count>half){
                return numbers[i];
            }
        }
        return 0;
    }
};