[剑指offer]刷题笔记

---

• 连续子数组的最大和（常见✔）

• 最小的k个数

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

• 数据流中的中位数（难♧）

---

连续子数组的最大和

题目描述：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

我的想法：

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int max=array[0];
        int sum=0;
        for(int i=0;i<array.size()-1;i++)
        {
            sum=array[i];
            for(int j=i+1;j<array.size();j++)
            {
                sum+=array[j];
                if(sum>max)
                    max=sum>max?sum:max;
            }
            max=array[i]>max?array[i]:max;  //不写这句话{-2，-8，-1，-5，-9}就只能指向-2
        }
        return max;
    }
};

smart的写法：
这题目应该是最基础的动态规划的题目：最大子数组的和一定是由当前元素和之前最大连续子数组的和叠加在一起形成的，因此需要遍历n个元素，看看当前元素和其之前的最大连续子数组的和能够创造新的最大值。

class Solution {
public:
   int FindGreatestSumOfSubArray(vector<int> array) {
       int len=array.size();
       int dp[len];
       dp[0]=array[0];
       int max=array[0];
       for(int i=1;i<len;i++)
       {
           if(dp[i-1]+array[i]>array[i])
               dp[i]=dp[i-1]+array[i];
           else
               dp[i]=array[i];
           max=dp[i]>max?dp[i]:max;
       }
       return max;
   }
};

基于思想：对于一个数A，若是A的左边累计数非负，那么加上A能使得值不小于A，认为累计值对整体和是有贡献的。如果前几项累计值负数，则认为有害于总和，total记录当前值。此时 若和大于maxSum 则用maxSum记录下来

public class Solution {
   public int FindGreatestSumOfSubArray(int[] array) {
       if(array.length==0)
           return 0;
       else{
           int total=array[0],maxSum=array[0];
           for(int i=1;i<array.length;i++){
               if(total>=0)
                   total+=array[i];
               else
                   total=array[i];
               if(total>maxSum)
                   maxSum=total;
           }
           return maxSum;
       }       
   }
}

---

最小的k个数

题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

我的方法（投机取巧）

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
         
        sort(input.begin(),input.end());
        vector<int> res;
        if(k==0||k>input.size())
            return res;
        for(int i=0;i<k;i++)
            res.push_back(input[i]);
        return res;
    }
};

更好的方法：利用堆排序，O(N logK)，适合处理海量数据
(1) 遍历输入数组，将前k个数插入到推中；（利用multiset来做为堆的实现）
(2) 继续从输入数组中读入元素做为待插入整数，并将它与堆中最大值比较：如果待插入的值比当前已有的最大值小，则用这个数替换当前已有的最大值；如果待插入的值比当前已有的最大值还大，则抛弃这个数，继续读下一个数。
这样动态维护堆中这k个数，以保证它只储存输入数组中的前k个最小的数，最后输出堆即可。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
    {
        vector<int> result;
        int len = input.size();
        if(input.empty() || k<=0 || len < k) return result;
         
        multiset<int, greater<int> > leastNumbers; // 从大到小排序
        multiset<int, greater<int> >::iterator iterGreater; // 定义迭代器
         
        vector<int>::iterator iter = input.begin();
        for(; iter != input.end(); ++iter)
        {
            // 将前k个数直接插入进multiset中，注意是小于K
            if(leastNumbers.size() < k)
            {
                leastNumbers.insert(*iter);
            }
            else
            {
                // 因为设置的从大到小排序，故multiset中第一个位置的元素即为最大值
                iterGreater = leastNumbers.begin();
                 
                // 如果input中当前元素比multiset中最大元素小，则替换；即保持multiset中这k个元素是最小的。
                if(*iter < *(leastNumbers.begin()))
                {
                    // 替换掉当前最大值
                    leastNumbers.erase(iterGreater); 
                    leastNumbers.insert(*iter);
                }
            }
        }
         
        for(iterGreater = leastNumbers.begin();iterGreater!=leastNumbers.end();++iterGreater)
        {
            result.push_back(*iterGreater); // 将multiset中这k个元素输出
        }
         
        return result;
    }
};

---

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

题目描述：例如数字输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在一段中出现了5次，超过一段长度的一半，因此输出2。如果不存在则输出0。

我的方法：

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

利用map：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n = numbers.size();
        //map 记录出现次数
        map<int, int> m;
        int count;
        for (int i = 0; i < n; i++) {
            count = ++m[numbers[i]];
            if (count > n/2) return numbers[i];
        }
        return 0;
    }
}

---

数据流中的中位数

题目描述：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

用到的知识点：【优先队列】

既然是队列那么先要包含头文件#include <queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。

基本操作：

• top 访问队头元素
• empty 队列是否为空
• size 返回队列内元素个数
• push 插入元素到队尾 (并排序)
• emplace 原地构造一个元素并插入队列
• pop 弹出队头元素
• swap 交换内容

定义：priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆，一般是：

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

数据流小于大根堆根节点则插入大根堆，否则插入小根堆，这样大根堆维护小的那一半，小根堆维护大的那一半.

//每次插入小顶堆的是当前大顶堆中最大的数`

//每次插入大顶堆的是当前小顶堆中最小的数`

//这样保证小顶堆中的数永远大于等于大顶堆中的数`

//中位数就可以方便地从两者的根结点中获取了`

class Solution {
public:
    void Insert(int num)
    {
        if (bigRootQueue.empty() || num <= bigRootQueue.top()) {
            bigRootQueue.push(num);
        } else {
            littleRootQueue.push(num);
        }
        if (bigRootQueue.size() > littleRootQueue.size() + 1) {
            littleRootQueue.push(bigRootQueue.top());
            bigRootQueue.pop();
        }
        if (littleRootQueue.size() > bigRootQueue.size()) {
            bigRootQueue.push(littleRootQueue.top());
            littleRootQueue.pop();
        }
    }
 
    double GetMedian()
    {
        int len = littleRootQueue.size() + bigRootQueue.size();
        if (len % 2) {
            return (double)bigRootQueue.top();
        } else {
            return (double)(bigRootQueue.top() + littleRootQueue.top()) / 2;
        }
    }
 
private:
    priority_queue<int, vector<int>, greater<int>> littleRootQueue;
    priority_queue<int, vector<int>, less<int>> bigRootQueue;
};