训练题：逆序对

题目：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

方法一：归并排序

  • 时间复杂度：O（nlogn）
  • 空间复杂度：O（n）

归并排序刚好是将左半有序部分和右半有序部分进行合并。在这个时候我们可以统计逆序对。

  2. int reversePairs(vector<int>& nums) {
  3.     if(nums.size() < 2) return 0;
  5.     const auto size = nums.size();
  7.     vector<int> tmpNums(size);
  8.     return mergeSort(nums, tmpNums, 0, size - 1);
  9. }
  11. int mergeSort(vector<int>& nums, vector<int>& tmpNums, int start, int end){
  12.     if(end <= start) return 0;
  14.     int mid   = start + ((end - start) >> 1);
  15.     int left  = start;
  16.     int right = mid + 1;
  17.     int k     = left;
  19.     int count = mergeSort(nums, tmpNums, start, mid) + mergeSort(nums, tmpNums, mid + 1, end);
  21.     for(; left <= mid && right <= end;)
  22.     {
  23.         if(nums[left] <= nums[right]) tmpNums[k++] = nums[left++];
  24.         else{   // left > right
  25.             tmpNums[k++] = nums[right++];
  27.             // 此时比num[right]大的数是num[left] ... num[mid]这几个数。
  28.             count += (mid - left + 1);
  29.         }
  30.     }
  32.     for(; left <= mid; ++left, ++k) tmpNums[k] = nums[left];
  33.     for(; right <= end; ++right, ++k) tmpNums[k] = nums[right];
  34.     copy( tmpNums.begin() + start, tmpNums.begin() + end + 1, nums.begin() + start );
  35.     return count;
  36. }

方法二：树状数组（待完成）

训练题：机器人运动范围

题目：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

方法一：深度优先遍历（递归）

  • 时间复杂度：O（mn）
  • 空间复杂度：O（mn）

算法训练_数组 - 图1

  2. int count;
  3. int tmp;
  4. int movingCount(int m, int n, int k) {
  5.     if(m < 1 || n < 1 || m > 100 || n > 100 || k < 0 || k > 20) return -1;
  7.     // dataMap用于记录遍历过的地方。
  8.     vector<vector<int>> dataMap(m, vector<int>(n, 0));
  9.     traverse(dataMap, m, n, k, 0, 0);
  10.     return count;
  11. }
  12. void traverse(int dataMap[][100], const int& m, const int& n, const int& k, int x, int y){
  13.     if( x == m || y == n || dataMap[x][y]) return;
  15.     dataMap[x][y] = 1;
  17.     tmp = x % 10 + x / 10 + y % 10 + y / 10;
  18.     if(tmp > k) return;
  20.     ++count;
  22.     // 优化：从上图我们看出规律：从左上往右下遍历，必然能全部遍历到。
  23.     // 往左（x-1）和往上（y-1）的遍历可以省去。
  24.     traverse(dataMap, m, n, k, x + 1, y);
  25.     traverse(dataMap, m, n, k, x, y + 1);
  26.     // traverse(dataMap, m, n, k, x - 1, y);
  27.     // traverse(dataMap, m, n, k, x, y - 1);
  28. }

方法二：广度优先遍历（队列）

  2. int movingCount(int m, int n, int k) {
  3.     if(m < 1 || n < 1 || m > 100 || n > 100 || k < 0 || k > 20) return -1;
  5.     int count = 0;                                        // 可到达的格子数
  6.     vector<vector<int>> dataMap(m, vector<int>(n, 0));    // 访问记录，避免重复
  7.     queue<pair<char, char>> q;                            // 广度优先
  9.     q.push({0, 0});
  11.     for(; !q.empty(); q.pop()){
  12.         auto pos = q.front();
  14.         // 无效坐标：坐标超范围、已经访问过、坐标值数位之和大于k的坐标。
  15.         if(pos.first == m || pos.second == n || dataMap[pos.first][pos.second]) continue;
  16.         if(pos.first % 10 + pos.first / 10 + pos.second % 10 + pos.second / 10 > k) continue;
  18.         ++count;
  19.         dataMap[pos.first][pos.second] = 1;
  21.         q.push({pos.first + 1, pos.second});
  22.         q.push({pos.first, pos.second + 1});
  23.     }
  25.     return count;
  26. }

方法三：递推法

  2. int movingCount(int m, int n, int k) {
  3.     if(m < 1 || n < 1 || m > 100 || n > 100 || k < 0 || k > 20) return -1;
  5.     int count = 0;
  6.     // canVisited[i][j] = canVisited[i-1][j] | canVisited[i][j-1]
  7.     // 即只能从左边或者上边的元素过来。
  8.     vector<vector<char>> canVisited(m, vector<char>(n, 0));
  9.     canVisited[0][0] = 1;
  11.     for(char row = 0; row < m; ++row){
  12.         for(char col = 0; col < n; ++col){
  13.             if(row%10 + row/10 + col%10 + col/10 > k) continue;
  14.             if(row - 1 >= 0) canVisited[row][col] |= canVisited[row-1][col];
  15.             if(col - 1 >= 0) canVisited[row][col] |= canVisited[row][col-1];
  16.             if(canVisited[row][col]) ++count;
  17.         }
  18.     }
  20.     return count;
  21. }

训练题：数组组成最小数

题目：http://t.cn/A6Vxkygn

  2. string minNumber(vector<int>& nums) {
  4.     const auto size = nums.size();
  5.     int len = 0;                    // nums的元素个数
  6.     int maxLen;                        // 最长元素长度
  7.     vector<string> strs;            // 将数字都转化成string
  8.     strs.reserve(size);
  10.     // 将所有数字转化成string
  11.     for(int i = 0, tmpLen; i < size; ++i) {
  12.         strs.push_back(to_string(nums[i]));
  13.         tmpLen = strs.back().size();
  14.         maxLen = max(maxLen, tmpLen);            // 记录最长元素
  15.         len += tmpLen;                            // 统计拼接成的string的总长度
  16.     }
  18.     // 对字符串数组进行排序，tmpStr1、tmpStr2是为了避免排序比较中的str1+str2<str2+str1的低性能代码。
  19.     string tmpStr1, tmpStr2;
  20.     tmpStr1.reserve(maxLen << 1);
  21.     tmpStr2.reserve(maxLen << 1);
  22.     sort(strs.begin(), strs.end(), [&](string &a, string &b) -> bool {
  24.         // "3"和"34"："334" < "343"
  25.         // "12"和9：    "129" < "912"
  26.         tmpStr1.resize(0);
  27.         tmpStr2.resize(0);
  28.         tmpStr1.append(a).append(b);
  29.         tmpStr2.append(b).append(a);
  30.         return tmpStr1 < tmpStr2;
  31.     });
  33.     // 将已排好序的vector<string>拼接成string
  34.     string ret;
  35.     ret.reserve(len);
  36.     for(const auto& str: strs) {
  37.         ret.append(str);
  38.     }
  40.     return ret;
  41. }

训练题：构建乘积数组

题目：http://t.cn/A65aO44I
算法训练_数组 - 图2

  2. vector<int> constructArr(vector<int>& a) {
  4.     const auto size = a.size();
  5.     vector<int> ret(size,1);
  7.     int left = 1, right = 1;
  8.     for(int i = 1; i < size; ++i){
  9.         ret[i] *= (left *= a[i - 1]);
  10.     }
  11.     for(int i = size - 2; i >=0; --i){
  12.         ret[i] *= (right *= a[i + 1]);
  13.     }
  15.     return ret;
  16. }

训练题：找数字

场景一：数组中数字出现的次数

题目：http://t.cn/A6A2wJLJ

  2. vector<int> singleNumbers(vector<int>& nums) {
  4.     int a = 0, b = 0;    // 待找出的两个数为a、b
  5.     int XOR = 0;        // XOR = a ^ b
  6.     int div = 1;        // div为XOR二进制数中最右边第一个1。
  8.     // XOR的最终结果为a 异或 b的结果，相同的两个数异或=0
  9.     for(const auto& num : nums) XOR ^= num;
  11.     // div为XOR二进制数中最右边第一个1。
  12.     while(!(XOR & div)) div <<= 1;
  13.     // div = (~XOR + 1) & XOR;
  14.     // div = XOR & (-XOR);        // 负数为补码，补码 = 反码 + 1。
  16.     // div表示，a、b在这个位上是不同的。我们以此来将数组分成两组分别进行异或即可找出这两个数。
  17.     for(const auto & num: nums) {
  18.         if(num & div) a ^= num;
  19.         else b ^= num;
  20.     }
  22.     return {a, b};
  23. }

场景二

题目：http://t.cn/A6qumpuV

  2. int singleNumber(vector<int>& nums) {
  4.     // 保存所有数字在32位的每个位上1出现的次数
  5.     unsigned short bits[32] = {0};
  6.     char offset = 0;
  7.     for(const auto& num : nums){
  8.         for(char offset = 0; offset < 32; ++offset) {
  9.             if(num & (1 << offset)) ++bits[offset];
  10.         }
  11.     }
  13.     // 设任意位上的次数=n，则若n%3==0，则表示目标数字在该位置上是0，反之则为1。
  14.     int fuck = 0;
  15.     for(char idx = 0; idx < 32; ++idx){
  16.         fuck |= (bits[idx] % 3) << idx;
  17.     }
  18.     return fuck;
  19. }

训练题：0~n-1中缺失的数

题目：http://t.cn/A6qjYvVx

  2. int missingNumber(vector<int>& nums) {
  4.     int left = 0;
  6.     // 二分查找法
  7.     for(int right = nums.size() - 1, mid; left <= right;){
  8.         mid = left + ((right - left) >> 1);
  10.         if(nums[mid] == mid) left = mid + 1;
  11.         else right = mid - 1;
  12.     }
  14.     return left;
  15. }

训练题：和为s的数

题目：http://t.cn/A6q3etqA

方法一：哈希表

  2. vector<int> twoSum(vector<int>& nums, int target) {
  3.     set<int> container;
  4.     for(const auto& num : nums){
  5.         if(container.count(num)){
  6.             return {target - num, num};
  7.         }
  8.         else container.insert(target - num);
  9.     }
  10.     return {};
  11. }

方法二：双指针

  2. vector<int> twoSum(vector<int>& nums, int target) {
  4.     for(int left = 0, right = nums.size() - 1; left < right;){
  5.         if(target - nums[left] == nums[right]) return {nums[left], nums[right]};
  6.         else if(target - nums[left] > nums[right]) ++left;
  7.         else --right;
  8.     }
  10.     return {};
  11. }

训练题：合并区间

题目：http://t.cn/A67wbdej

按区间的左元素升序排序，得到的区间序列，其中连续的区间肯定是在一块的。

  2. vector<vector<int>> merge(vector<vector<int>>& intervals) {
  4.     if(intervals.size() < 2) return intervals;
  6.     sort(intervals.begin(), intervals.end());
  7.     vector<vector<int>> ret{intervals[0]};
  9.     vector<int> *tmp = nullptr;
  10.     for(const auto& vec : intervals)
  11.     {
  12.         tmp = &ret.back();
  13.         if((*tmp)[1] >= vec[0]) (*tmp)[1] = max((*tmp)[1], vec[1]);
  14.         else ret.push_back(vec);
  15.     }
  17.     return ret;
  18. }

训练题：搜索插入位置

题目：http://t.cn/A6hOM5MX

  2. int searchInsert(vector<int>& nums, int target) {
  3.     int left = 0;
  4.     for(int right = nums.size() - 1, mid; left < right;)
  5.     {
  6.         mid = ((left + right) >> 1);
  7.         if(nums[mid] == target) return mid;
  8.         else if(nums[mid] > target) right = mid;
  9.         else left = mid + 1;
  10.     }
  11.     if(nums[left] < target) return left + 1;
  12.     return left;
  13. }

训练题：中心下标

题目：http://t.cn/A65IN4vg

  2. // leftSum:    左边和
  3. // idx:        当前遍历索引，左边就是左边和
  4. // total:    数组总和
  5. // leftSum * 2 + nums[idx] == total
  6. int pivotIndex(vector<int>& nums) {
  8.     int sum = 0, leftSum = 0;
  9.     for(const auto& num : nums) sum += num;
  11.     unsigned short size = nums.size();
  12.     for(unsigned short idx = 0; idx < size; ++idx)
  13.     {
  14.         if((leftSum * 2) + nums[idx] == sum) return idx;
  15.         leftSum += nums[idx];
  16.     }
  18.     return -1;
  19. }

训练题：奇数在偶数的前面

题目：http://t.cn/A6b1uvbE

方法一：双指针

  2. vector<int> exchange(vector<int>& nums) {
  3.     if( nums.size() < 2 ) { return nums; }
  5.     // 快速排序的partition分区思想。
  6.     for( unsigned short left = -1, right = nums.size();; )
  7.     {
  8.         while( ++left < right && (nums[left] & 0x1) );
  9.         while( --right > left && !(nums[right] & 0x1) );
  10.         if( left < right ) { std::swap( nums[left], nums[right] ); }
  11.         else { break; }
  12.     }
  14.     return nums;
  15. }

方法二：快慢指针

  • slow指向待插入奇数的位置。
  • fast指向找到的奇数 ```cpp

vector exchange(vector& nums) { if( nums.size() < 2 ) { return nums; }

  1. const auto size = nums.size();
  2. for( unsigned short slow = 0, fast = 0;; )
  3. {
  4.     while( fast < size && !( nums[fast] & 0x1 ) ) { ++fast; }
  6.     if( fast < size ) { std::swap( nums[fast++], nums[slow++] ); }
  7.     else { break; }
  8. }
  10. return nums;

}

  1. <a name="FCNIY"></a>
  2. # 训练题：旋转数组的最小数字
  3. 题目：[http://t.cn/A6V4bma7](http://t.cn/A6V4bma7)
  4. ```cpp
  6. int minArray(vector<int>& numbers) {
  7.     if(numbers.empty()) return INT_MIN;
  9.     int left = 0, right = numbers.size() - 1, mid;
  10.     for(;left < right;){
  12.         mid = left + ((right - left) >> 1);
  14.         if(numbers[mid] < numbers[right]) right = mid;
  15.         else if(numbers[mid] == numbers[right]) right -= 1;
  16.         else left = mid + 1;
  18.     }
  19.     return numbers[left];
  20. }

训练题：重复的数字

题目：http://t.cn/A62yf09c

方法一

遍历数组的过程中，让nums[idx]的值在nums[nums[idx]]位置上，即元素值和索引值相同。
时间复杂度：O(n)
空间复杂度：O(1)

  2. int findRepeatNumber(vector<int>& nums) {
  3.     const auto size = nums.size();
  4.     for( int idx = 0; idx < size; ++idx )
  5.     {
  6.         if( idx != nums[idx] )
  7.         {
  8.             if( nums[idx] == nums[nums[idx]] ) { return nums[idx]; }
  9.             else { std::swap( nums[nums[idx]], nums[idx] ); }
  10.         }
  11.     }
  12.     return -1;
  13. }

方法二：set集合

时间复杂度：O(n)
空间复杂度：O(n)

  2. int findRepeatNumber(vector<int>& nums) {
  3.     set<int> shit;
  5.     for( auto &num : nums )
  6.     {
  7.         if( shit.count( num ) ) { return num; }
  8.         else { shit.insert( num ); }
  9.     }
  10.     return -1;
  11. }

训练题：超过一半的数字

题目：http://t.cn/A6V459Fx

方法一：排序

先排序，然后返回中间那个数，这里我们假设一定存在这样一个数。

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)

方法二：哈希

用一个哈希统计每个数出现的次数。

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
  2. int MoreThanHalfNum_Solution( vector<int> numbers )
  3. {
  4.     map<int, unsigned short> shit;
  5.     const auto size = numbers.size() >> 1;
  6.     for( const auto &num : numbers ) if( ++shit[num] > size ) { return num; }
  7.     return -1;
  8. }

方法三

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
  2. int MoreThanHalfNum_Solution( vector<int> numbers )
  3. {
  4.     unsigned short size  = numbers.size();
  6.     // 遍历数组，当target与当前数不同，count-1，count=0，就将target赋值为当前数
  7.     // 当target与当前数相同则count+1，遍历到最后一个数，target必定为目标数
  8.     unsigned short count = 1;                // 
  9.     int target           = numbers[0];        // 当前数目
  10.     for( unsigned short idx = 1; idx < size ; ++idx )
  11.     {
  12.         target == numbers[idx] ? ++count : --count;
  13.         if( !count )
  14.         {
  15.             target = numbers[idx];
  16.             count = 1;
  17.         }
  18.     }
  19.     return target;
  20. }

训练题：两数之和

题目：http://t.cn/A6Vzz5Cd

  2. typedef int Value;
  3. typedef int Index;
  4. /**
  5. * 
  6. * @param numbers int整型vector 
  7. * @param target int整型 
  8. * @return int整型vector
  9. */
  10. vector<int> twoSum( vector<int> &numbers, int target )
  11. {
  12.     if( numbers.size() < 2 ) { return {}; }
  14.     map<Value, Index> shit;
  16.     int index2 = -1;
  17.     for( int index1 = 0; index1 < numbers.size(); index1++ )
  18.     {
  19.         if( shit.find( target - numbers[index1] ) != shit.end() )
  20.         {
  21.             index2 = shit[target - numbers[index1]];
  22.             return {index2 + 1, index1 + 1};
  23.         }
  24.         shit.insert( make_pair( numbers[index1], index1 ) );
  25.     }
  26.     return{};
  27. }

训练题：三数之和

题目：https://leetcode-cn.com/problems/3sum/

方法一：降维成两数之和

  2. vector<vector<int>> threeSum(vector<int>& nums) {
  3.     if(nums.size() < 3) return {};
  5.     sort(nums.begin(), nums.end());
  7.     if(nums[0] > 0) return {};
  9.     const auto size = static_cast<short>(nums.size());
  10.     vector<vector<int>> ret;
  12.     for(short first = 0; first < size - 2; ++first){
  13.         // 先取第一个数，问题就变成在数组中找两数之和的问题，用双指针搞定。
  15.         // 当前取的first和上一轮的相同，那这个first就重复了。
  16.         if(first > 0 && nums[first] == nums[first - 1]) continue;
  18.         int target = 0 - nums[first];               // 目标和
  19.         int left = first + 1, right = size - 1;     // 左右指针
  21.         while(left < right){
  23.             // 这里其实还
  24.             if(nums[left] + nums[right] < target) ++left;           // 右移左指针
  26.             else if(nums[left] + nums[right] > target) --right;     // 左移右指针
  28.             else{                                                   // 找到目标
  29.                 ret.push_back({nums[first], nums[left++], nums[right--]});
  31.                 // 排序之后，相等的数都相邻，找到目标之后，需要做去重操作。
  32.                 for(; left < right && nums[left] == nums[left-1]; ++left);      // 当前的left指针和目标和的left指针相同，跳过
  33.                 for(; left < right &&nums[right] == nums[right+1]; --right);    
  34.             }
  35.         }
  36.     }
  38.     return ret;
  39. }

训练题：最接近三数之和

题目：https://leetcode-cn.com/problems/3sum-closest/

同上理。

  2. int threeSumClosest(vector<int>& nums, int target) {
  4.     sort(nums.begin(), nums.end());
  6.     const auto size = nums.size();
  7.     int ret = nums[0] + nums[1] + nums[2];
  9.     if(ret == target) return ret;
  11.     for(int first = 0; first < size - 2; ++first){
  12.         if(first > 0 && nums[first] == nums[first - 1]) continue;
  14.         for(int left = first+1, right = size - 1, tmpSum; left < right; ) {
  15.             tmpSum = nums[first] + nums[left] + nums[right];
  17.             if(tmpSum == target) return target;
  18.             else {
  19.                 if(abs(ret - target) > abs(tmpSum - target)) ret = tmpSum;
  20.                 if(tmpSum > target) for(--right; left < right && nums[right] == nums[right+1]; --right);
  21.                 else for(++left; left < right && nums[left] == nums[left-1]; ++left);
  22.             }
  23.         }
  24.     }
  26.     return ret;
  27. }

训练题：最大累加和

题目：http://t.cn/A6qIcLYu

动态规划。
连续子数组的最大累加和肯定是以某个元素结尾。
我们设dp[i]是以i位置元素结尾的最大累加和。按dp思想，我们就要从dp[i-1]来求dp[i]。

算法训练_数组 - 图3

  2. int maxSubArray(vector<int>& nums) {
  3.     int maxSum = nums[0];    // 当前的最大累加和。
  4.     for(int i = 1; i < nums.size(); i++){
  6.         // nums[i]存储以nums[i]元素结尾的连续最大累加和。
  8.         // 如果nums[i - 1]<=0，则nums[i]的最大累加和就等于nums[i]元素，
  9.         // 如果nums[i - 1]>0,则nums[i]的最大累加和=nums[i-1] + nums[i]
  10.         nums[i] += max(nums[i - 1], 0);
  12.         // 比较当前记录的最大累加和，和nums[i]位置处的最大累加和。
  13.         maxSum = max(maxSum, nums[i]);
  14.     }
  15.     return maxSum;
  16. }

训练题：合并有序数组

题目：http://t.cn/A6VZoOZ2

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
  2. void merge(int A[], int m, int B[], int n) {
  4.     // 逆序遍历A、B数组。将最大者保存到tail中
  5.     for( int tail = m + n - 1, tailA = m - 1, tailB = n - 1; tail >= 0; --tail )
  6.     {
  7.         if( tailA >= 0 && ( tailB < 0 || B[tailB] < A[tailA] ) )
  8.         {
  9.             A[tail] = A[tailA--];
  10.         }
  11.         else
  12.         {
  13.             A[tail] = B[tailB--];
  14.         }
  15.     }
  16. }

训练题：有序数组查找数字

二分查找算法

有序数组查找数字，就不得不想到二分查找法。
二分查找算法的使用心得，将left、right、mid当成二分搜索的动力，nums[mid]与target比较时，mid的赋值决定了搜索的方向（如果找到相同的，是往右边继续搜，还是往左边）。

  2. // nums是升序的，target是需要找的数字
  3. // 返回目标数字在数组nums中的索引，如果没有找到返回-1
  4. int search(vector<int>& nums, int target) {
  6.     int left = 0, right = nums.size() - 1;
  8.     for(int mid; left <= right;) {
  10.         // 可选逻辑：先行判断，减少计算量
  11.         if(nums[left] == target) return left;
  12.         else if(nums[right] == target) return right;
  14.         // 写成mid = (left + right) >> 1有整型溢出风险。
  15.         // >>位移运算符的优先级很低，请加括号
  16.         mid = left + ((right - left) >> 1);
  18.         if(nums[mid] == target) return mid;
  19.         else if(nums[mid] > target) right = mid - 1;
  20.         else left = mid + 1;
  21.     }
  23.     // 到这一步，left > right，没有找到。
  24.     return -1;
  25. }

算法变形一

  2. // nums是升序的，找到target从索引0开始的第一次出现时的索引，没有返回-1。
  3. // 找区域的左边界。
  4. int search(vector<int>& nums, int target) {
  6.     int start = -1;
  8.     for(int left = 0, right = nums.size() - 1, mid; left <= right;){
  10.         mid = left + ((right - left) >> 1);
  12.         if(nums[mid] == target) start = mid;
  13.         if(nums[mid] >= target) right = mid - 1;    // 找到相同的，继续往左边搜。
  14.         else left = mid + 1;
  15.     }
  17.     return start;
  18. }

算法变形二

  2. // nums是升序的，找到target从末尾往前第一次出现的索引。不存在返回-1
  3. // 找区域的右边界。
  4. int search(vector<int>& nums, int target) {
  6.     int end = -1;
  8.     for(int left = 0, right = nums.size() - 1, mid; left <= right;){
  10.         mid = left + ((right - left) >> 1);
  12.         if(nums[mid] == target) end = mid;
  13.         if(nums[mid] <= target) left = mid + 1;        // 找到相同的继续往右边搜。
  14.         else right = mid - 1;
  15.     }
  17.     return end;
  18. }

场景一：查找数字

题目：http://t.cn/A6V45X5T

  2. int search(vector<int>& nums, int target) {
  4.     int targetIdx = -1;
  6.     for( int left = 0, right = nums.size() - 1, mid; left <= right; )
  7.     {
  8.         mid = left + ((right - left) >> 1);
  10.         if(nums[mid] == target) ret = mid;
  11.         if(nums[mid] >= target) right = mid - 1;
  12.         else { left = mid + 1; }
  13.     }
  15.     return targetIdx;
  16. }

场景二：搜索插入位置

题目：http://t.cn/A6hOM5MX

  2. int searchInsert(vector<int>& nums, int target) {
  4.     int targetIdx = 0;
  6.     for(int left = 0, right = nums.size() - 1, mid; left <= right;){
  8.         mid = left + ((right - left) >> 1);
  10.         if(nums[mid] == target) return mid;
  12.         if(nums[mid] > target) targetIdx = mid;
  13.         else targetIdx = mid + 1;
  15.         if(nums[mid] > target) right = mid - 1;
  16.         else left = mid + 1;
  17.     }
  19.     return targetIdx;
  20. }

场景三：统计数字个数

题目：http://t.cn/A6qjjjXp

  3. int search(vector<int>& nums, int target) {
  5.     // 通过二分查找法找到target区域的左右边界
  6.     int targetLeftIdx = -1, targetRightIdx = -1;
  8.     // 找左边界
  9.     for(int left = 0, right = nums.size() - 1, mid; left <= right;){
  11.         mid = left + ((right - left) >> 1);
  13.         if(nums[mid] == target) targetLeftIdx = mid;
  14.         if(nums[mid] >= target) right = mid - 1;
  15.         else left = mid + 1;
  16.     }
  18.     // 找到右边界
  19.     for(int left = 0, right = nums.size() - 1, mid; left <= right;){
  21.         mid = left + ((right - left) >> 1);
  23.         if(nums[mid] == target) targetRightIdx = mid;
  24.         if(nums[mid] <= target) left = mid + 1;
  25.         else right = mid - 1;
  26.     }
  28.     // 没有找到target
  29.     if(targetLeftIdx == -1) return 0;
  31.     // 找到target，索引相减 + 1
  32.     return targetRightIdx - targetLeftIdx + 1;
  33. }

训练题：移动零

题目：https://leetcode-cn.com/problems/move-zeroes/

  2. void moveZeroes(vector<int>& nums) {
  3.     if(nums.size() < 2) return;
  5.     const auto size = nums.size();
  7.     // 双指针
  8.     // p_0:        指向从头开始的第一个0。
  9.     // p_num:    指向p_0之后的第一个非零数字。
  10.     int p_0 = 0, p_num = 0;
  12.     // 指向第一个0
  13.     for(; p_0 < size && nums[p_0] != 0; ++p_0);
  14.     p_num = p_0 + 1;
  16.     while(true){
  18.         // 指向第一个0
  19.         for(; p_0 < size && nums[p_0] != 0; ++p_0);
  21.         // 指向p_0之后的第一个非0
  22.         for(; p_num < size && nums[p_num] == 0; ++p_num);
  24.         // 交换了之后，p_0肯定是非0，p_num肯定是0。
  25.         // 因此将p_0和p_num右移一位
  26.         if(p_0 < size && p_num < size) swap(nums[p_0++], nums[p_num++]);
  27.         else break;
  28.     }
  29. }
  2. void moveZeroes(vector<int>& nums) {
  4.     const auto size = nums.size();
  5.     int left = 0, right = 0;
  7.     // left:    left指向第一个非0
  8.     // right:    right指向第一个0。
  9.     for(int left = 0, right = 0; right < size; ++right){
  10.         if(nums[right]) swap(nums[right], nums[left++]);
  11.     }
  12. }

训练题：两个正序数组的中位数

题目：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

方法一：模拟法

遍历中位数的位置。

  2. double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  3.     if(nums1.empty() && nums2.empty()) return 0;
  5.     const auto size1 = nums1.size();
  6.     const auto size2 = nums2.size();
  8.     // 设：
  9.     //         nums1 = [1, 3, 5];
  10.     //        nums2 = [2, 4, 6];
  11.     //         remainCount = 4;
  12.     // 按从小到大的顺序，移动tmpIdx1、tmpIdx2索引，得：
  13.     //         tmpIdx1 = 2，即移动到了tmpIdx1-1=1索引处，为3。
  14.     //         tmpIdx2 = 2，即移动到了tmpIdx2-1=1索引处，为4。
  15.     int remainCount = ((size1 + size2) >> 1) + 1;
  16.     int tmpIdx1 = 0, tmpIdx2 = 0;    
  18.     for(; tmpIdx1 < size1 && tmpIdx2 < size2 && remainCount ; --remainCount){
  19.         if(nums1[tmpIdx1] < nums2[tmpIdx2]) ++tmpIdx1;
  20.         else ++tmpIdx2;
  21.     }
  23.     if(remainCount && tmpIdx1 < size1) tmpIdx1 += remainCount;
  24.     if(remainCount && tmpIdx2 < size2) tmpIdx2 += remainCount;
  26.     // 若为奇数，则取tmpIdx1-1和tmpIdx2-1索引处更大者。
  27.     if((size1 + size2) & 1) {
  28.         if(tmpIdx1 > 0 && tmpIdx2 > 0) return max(nums1[tmpIdx1-1], nums2[tmpIdx2-1]);
  29.         if(tmpIdx1 > 0) return nums1[tmpIdx1-1];
  30.         return nums2[tmpIdx2-1];
  31.     }
  32.     else{
  33.         // 若为偶数，则取tmpIdx-1、tmpIdx1-2、tmpIdx2-1、tmpIdx2-2中最大的两个。
  34.         priority_queue<int> q;
  35.         if(tmpIdx1 > 0) q.push(nums1[tmpIdx1-- - 1]);
  36.         if(tmpIdx1 > 0) q.push(nums1[tmpIdx1 - 1]);
  37.         if(tmpIdx2 > 0) q.push(nums2[tmpIdx2-- - 1]);
  38.         if(tmpIdx2 > 0) q.push(nums2[tmpIdx2 - 1]);
  40.         int mid1 = q.top();
  41.         q.pop();
  42.         return (mid1 + q.top()) / 2.0;
  43.     }
  44. }

方法二：模拟法

  2. class Solution {
  3. public:
  4.     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  5.         if(nums1.empty() && nums2.empty()) return 0;
  7.         const auto size1 = nums1.size();
  8.         const auto size2 = nums2.size();
  10.         int remainCount = (size1 + size2) / 2 + 1;
  11.         int tmpIdx1 = 0, tmpIdx2 = 0;
  13.         for(; tmpIdx1 < size1 && tmpIdx2 < size2 && remainCount ; --remainCount){
  14.             if(nums1[tmpIdx1] < nums2[tmpIdx2]) ++tmpIdx1;
  15.             else ++tmpIdx2;
  16.         }
  18.         if(remainCount && tmpIdx1 < size1) tmpIdx1 += remainCount;
  19.         if(remainCount && tmpIdx2 < size2) tmpIdx2 += remainCount;
  21.         if((size1 + size2) & 1) {
  22.             if(tmpIdx1 > 0 && tmpIdx2 > 0) return max(nums1[tmpIdx1-1], nums2[tmpIdx2-1]);
  23.             if(tmpIdx1 > 0) return nums1[tmpIdx1-1];
  24.             return nums2[tmpIdx2-1];
  25.         }
  26.         else{
  28.             // 与上一种方法的区别主要在于偶数情况时的动作。
  30.             // 去tmpIdx1-1和tmpIdx1-2的情况有两种
  31.             //        一、tmpIdx2无效
  32.             //        二、tmpIdx>1且tmpIdx2-1<tmpIdx1-2
  33.             if(tmpIdx1 > 0 && tmpIdx2 == 0 || tmpIdx1 > 1 && tmpIdx2 > 0 && nums2[tmpIdx2-1] <= nums1[tmpIdx1-2]) 
  34.                 return (nums1[tmpIdx1-1] + nums1[tmpIdx1-2]) / 2.0;
  35.             else if(tmpIdx2 > 0 && tmpIdx1 == 0 || tmpIdx2 > 1 && tmpIdx1 > 0 && nums1[tmpIdx1-1] <= nums2[tmpIdx2-2]) 
  36.                 return (nums2[tmpIdx2-1] + nums2[tmpIdx2-2]) / 2.0;
  37.             return (nums1[tmpIdx1 - 1] + nums2[tmpIdx2-1]) / 2.0;
  38.         }
  39.     }
  41. };

方法三：模拟法

  2. double findMedianSortedArrays( vector<int> nums1, vector<int> nums2 )
  3. {
  4.     const auto size1 = static_cast<int>( nums1.size() );
  5.     const auto size2 = static_cast<int>( nums2.size() );
  6.     bool even = ( ( size1 + size2 ) & 1 ) == 0;
  8.     if( size1 == 0 && size2 == 0 ) { return 0; }
  9.     if( size1 == 1 && size2 == 1 ) { return ( nums1[0] + nums2[0] ) / 2.0; }
  10.     if( size1 == 0 ) { return even ? ( nums2[size2 >> 1] + nums2[( size2 - 1 ) >> 1] ) / 2.0 : nums2[( size2 >> 1 )] ; }
  11.     if( size2 == 0 ) { return even ? ( nums1[size1 >> 1] + nums1[( size1 - 1 ) >> 1] ) / 2.0 : nums1[( size1 >> 1 )] ; }
  13.     int remainCount = ( size1 + size2 ) / 2 + 1;
  14.     int val1        = 0, val2    = 0;
  15.     int tmpIdx1     = 0, tmpIdx2 = 0;
  17.     for( ; tmpIdx1 < size1 && tmpIdx2 < size2 && remainCount; --remainCount )
  18.     {
  19.         if( even ) { val2 = val1; }
  21.         if( nums1[tmpIdx1] < nums2[tmpIdx2] ) { val1 = nums1[tmpIdx1++]; }
  22.         else { val1 = nums2[tmpIdx2++]; }
  23.     }
  25.     for( ; tmpIdx1 < size1 && remainCount; --remainCount, ++tmpIdx1 )
  26.     {
  27.         if( even ) { val2 = val1; }
  28.         val1 = nums1[tmpIdx1];
  29.     }
  31.     for( ; tmpIdx2 < size2 && remainCount; --remainCount, ++tmpIdx2 )
  32.     {
  33.         if( even ) { val2 = val1; }
  34.         val1 = nums2[tmpIdx2];
  35.     }
  37.     if( !even ) { return val1; }
  38.     else { return ( val1 + val2 ) / 2.0; }
  39. }