1.1题目描述 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示列： 输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。
提示： 1 <= nums.length <= 50000 1 <= nums[i] <= 10000
1.2题目分析 方法一：利用快慢指针
定义两个指针low和fast,都从下标为0的位置开始只要fast没有数组越界，fast指针一直向前遍历遇到low指针的元素是偶数并且fast指向的元素是奇数就交换这两个指针所指向的值只有遇到low指向的元素不是偶数的时候，low指针才往前遍历以例子数组【1234】来说，具体的过程如下： 代码实现：
void swap(int& a, int& b) { int temp = a; a = b; b = temp; } vector<int> exchange(vector<int>& nums) { int low = 0; int fast = 0; while (fast < nums.size()) { if (nums[low] % 2 == 0 && nums[fast] % 2 != 0) { swap(nums[low], nums[fast]); } if (nums[low] % 2 != 0) { low++; } fast++; } return nums; }方法二：双指针
定义两个指针low和high。low从数组的头部开始找偶数，high从数组的尾部开始找奇数直到low>=high时退出寻找代码实现：
vector<int> exchange1(vector<int>& arr) { int low = 0; int high = arr.size() - 1; while (low < high) { if (arr[low] % 2 != 0) { low++; continue; } if (arr[high] % 2 == 0) { high--; continue; } swap(arr[low], arr[high]); } return arr; } int main() { vector<int> res; vector<int> a; res.push_back(1); res.push_back(2); res.push_back(3); res.push_back(4); a = exchange1(res); for (int i = 0; i < a.size(); i++) { cout << a[i] << endl; } return 0; }1、题目要求 统计一个数字在排序数组中出现的次数。
示例1 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2
示例2 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0
2、题目分析 方法一：挨个遍历查询 这样做的时间复杂度最高，可达O(n)
int search(vector<int>& nums, int target) { int count = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] == target) count++; } return count; }方法二：巧用二分查找 基于上一个方法时间复杂度太高，并且没有充分利用数组排序的特点，所以采用二分查找的方式来求解，时间复杂度是O(logn)
定义两个指针，low指向数组的头部，high指向数组的尾部利用二分查找的方式，判断数组中间mid所指的数字是否和目标元素相同如果相同的话，利用数组排序的特点，目标元素的相邻元素一定和目标元素是相同的，分别在左右子数组中统计和目标数字相同的数字个数Lcount和Rcount最后返回值为Lcount+Rcount+1具体的，以下面以 nums = [5,7,7,8,8,10], target = 8这个例子加以分析 注意！！ 还有特殊情况的处理，如果数组中没有元素应该return -1
int search1(vector<int>& arr, int target) { if (arr.size() == 0) { return -1; } int low = 0; int high = arr.size() - 1; int countL = 0; int countR = 0; int count = 0; while (low <= high) { int mid = (high - low + 1) / 2 + low; if (arr[mid] < target) low = mid + 1; else if (arr[mid] > target) high = mid - 1; else//找到了，因为是排序数组，则相同的元素就在该元素的左右两边 { int Lhigh = mid ; int Rlow = mid ; while (Lhigh > low&& arr[--Lhigh] == target) { countL+=1; } while (Rlow < high && arr[++Rlow] == target) { countR+=1; } count = countL + countR + 1; break; } } return count; }1、题目要求 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例1： 输入: [0,1,3] 输出: 2
示例2： 输入: [0,1,2,3,4,5,6,7,9] 输出: 8
限制：1 <= 数组长度 <= 10000
2、题目分析 注意！ ：[0,1]表示数组长度为n-1=2，所以n=3，共有3个数字，所以在{0，3}之间的是[0,1,2]；不能理解为只有2个数字，不缺失数字。这一点很重要。 方法一：两次循环
第一次循环得到0~n-1的总和sum1,第二次循环得到数组元素的总和sum2返回sum1-sum2，即为缺失的那个数但是这种方法不可取，时间复杂度太高，没有充分利用数组有序的特点 代码实现： int missingNumber(vector<int>& arr) { if (arr.size() == 0) return -1; int sum1 = 0; int sum2 = 0; for (int i = 0; i <= arr.size(); i++) { sum1 += i; } for (int j = 0; j < arr.size(); j++) { sum2 += arr[j]; } return sum1 - sum2; }方法二：一次循环
根据数组排列有序的特点。没有缺失的数字一定是和其下标一一对应的如果遇到没有对应的数字则表示该下标对应的数字缺失如果数组遍历完毕都没找到缺失的数字，说明是数组最后一个数字缺失。返回arr.size()的值代码实现如下：
int missingNumber1(vector<int>& arr) { for (int i = 0; i < arr.size(); i++) { if (i != arr[i]) return i; } return arr.size(); }方法三：二分查找
二分查找的思路还是根据下标和数组中的值来判断缺失元素。但是相比于方法三更好的是一次可以舍弃一半的数据
如果==mid等于arr[mid]==的值相等的话，表示在mid之前都是按照顺序没有缺失存放的，那么就在后半边数组中去寻找，high = mid+1.
如果mid和arr[mid]的值不相等的话。比较mid-1和arr[mid-1]的值是否相等 3.1如果相等就表示mid即为缺失的数字 3.2如果不相等，则表示缺失的值，在mid前面。让high = mid-1
查找到最后返回值的探讨。返回值不应该是mid。比如下面这个例子
所以二分查找跳出循环过后需要返回low,而不是mid.
代码实现如下：
int missingNumber2(vector<int>& arr) { if (arr.size() == 0) return -1; int low = 0; int high = arr.size() - 1; while(low <= high) { int mid = (high - low + 1) / 2 + low; if (mid == arr[mid])//左半部分没有问题 { low = mid + 1; } else//左半部分有问题 { if (low > 0 && mid - 1 == arr[mid - 1]) return mid; else high = mid - 1; } } return low; } int main() { vector<int> res; res.push_back(0); res.push_back(1); res.push_back(2); res.push_back(3); res.push_back(4); res.push_back(5); cout << missingNumber2(res) << endl; return 0; }