排序

1. 實(shí)現(xiàn)歸并排序、快速排序、插入排序、冒泡排序、選擇排序、堆排序（選做）（完成leetcode上的返回滑動(dòng)窗口中的最大值(239)，這是上一期第三天的任務(wù)進(jìn)行保留（涉及隊(duì)列可以對第二天進(jìn)行整理復(fù)習(xí)））

2. 編程實(shí)現(xiàn) O(n) 時(shí)間復(fù)雜度內(nèi)找到一組數(shù)據(jù)的第 K 大元素

int selectKthNum(vector<int> &vi, int low, int up, int k)
{
   int p =  up - low +1;
   if(p<6)
   {
    sort(vi.begin()+low, vi.begin()+up+1);
    return vi[k-1];
   }
   int q = p/5; 
   vector<int> medVec;
   int mid = q/2;
   for (int i = 0; i < 5; i++)
   {
      int m = selectKthNum(vi, i*q, (i+1)*q-1,mid+1);
      medVec.push_back(m);
   }
 
   int mNum = selectKthNum(medVec, 0, 
                      medVec.size()-1,   medVec.size()/2+1);

   vector<int> vec1, vec2, vec3;
   for (int i = low; i <= up; i++)
    {
      if(vi[i] > mNum) vec3.push_back(vi[i]);
      if(vi[i] == mNum) vec2.push_back(vi[i]);
      if(vi[i] < mNum) vec1.push_back(vi[i]);
    }
 
   if(vec1.size()>=k) 
      return selectKthNum(vec1, 0, vec1.size()-1, k);
   else if(vec1.size()+vec2.size()>=k) 
      return mNum;
   else if(vec1.size()+vec2.size()<k) 
      return selectKthNum(vec3, 0, vec3.size()-1, 
                                    k-vec1.size()-vec2.size());
}

二分查找

1. 實(shí)現(xiàn)一個(gè)有序數(shù)組的二分查找算法

2. 實(shí)現(xiàn)模糊二分查找算法（比如大于等于給定值的第一個(gè)元素）

對應(yīng)的 LeetCode 練習(xí)題

Sqrt(x) （x 的平方根）

英文版：https://leetcode.com/problems/sqrtx/

中文版：https://leetcode-cn.com/problems/sqrtx/

class Solution {
public:
    int mySqrt(int x) {
        if(x <= 0)
            return 0;
        if(x == 1)
            return 1;
        int i = 1, r = x / 2;
        long mid = 0, t = 0;
        while(i <= r) {
            mid = (i + r) / 2;
            t = mid * mid;
            if(t == x)
                return mid;
            else if(t > x)
                r = mid - 1;
            else
                i = mid + 1;
        }
        return r; 

    }
};