剑指offer经典题型（一）

        本期我们将开始进行剑指offer中经典题型的学习。

数组相关

        题目1：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。OJ地址

        分析：所有的查找本质上就是一个排除的过程，一次排除的无效元素越多，查找的效率就越高。 

        解题思路：二维矩阵的右上角的元素，一定是它所处的行中最大的元素，所处的列中最小的元素。 以右上角的元素为基准，依次与此元素进行比较，比当前元素小就在当前元素的左侧进行查找，比当前元素大就在当前元素的下侧进行查找。多次的查找就是一个循环，所以需要以行标和列标作为循环的终止条件。通过上述查找方式，一次可以排除一行或者一列，所以效率也是很高的。

        代码如下。

class Solution {
public:bool Find(int target, vector<vector<int> >& array) {//i表示二维数组的行标，由最外层的vector对象array的元素的个数size()决定int i=0;//j表示二维数组的列标，由里层的每个vector对象的元素的个数size()决定int j=array[0].size()-1;while(i<array.size()&&j>=0){if(target<array[i][j]){j--;}else if(target>array[i][j]){i++;}else {return true;}}return false;}
};

        题目2： 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。oj地址

        解题思路： 一个非递减的数组在进行了旋转之后，一定一定一定会被分成左右两个非递增的数据，且左边的递增数组的所有元素的值一定是 >= 右边递增数组的所有元素的。且旋转的数组的最小值一定就是首次出现递减的时候的最小值。那么怎样才能知道首次递减呢，我们可以通过二分查找的方式，每次确定一个mid，然后一次比较mid和left的值，如果mid的值比left的值大或者相等，那么mid一定在左侧的非递减序列中，那么最小的值一定在mid的右侧，所以此时就要调整left的值为mid的值，即left右移；如果mid的值比左侧的值小，那么mid一定处于右侧的非递减序列，那么最小的值一定是在mid的左侧的，或者mid就是最小值，所以此时我们就要调整right的值为mid的值，即right左移。当left和right相邻时，right的值就是最大值。

        特殊情况：当这个数组的每个元素都是相等的时候，也就是无法通过mid与left或者right的值去判断，最小的值在mid的左侧或者右侧时，此时就要现行便利旋转之后的数组去查询最小值。

        代码如下。

class Solution {
public:int minNumberInRotateArray(vector<int>& nums) {//如果nums的size为0，则直接返回0if(nums.size()==0){return 0;}int left=0;int right=nums.size()-1;//旋转数组的条件就是left的值比right的值大while(nums[left]>=nums[right]){int mid=(left+right)/2;//right和left相邻时，right对应的值就是最小值if(right-left==1){return nums[right];}//如果通过mid与left或者right比较之后确定最小值的位置，则要通过线性遍历，确定最小值if(nums[left]==nums[mid]&&nums[mid]==nums[right]){int result=nums[left];for(int i=1;i<nums.size();i++){if(result>nums[i]){result=nums[i];}}return result;}//如果mid的值大于left，证明最小的值在mid右侧，右移leftif(nums[mid]>=nums[left]){left=mid;}//如果mid的值小于left，证明最小的值在mid左侧，左移rightelse {right=mid;}}return nums[left];}
};

        题目3： 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

        解析：如上图要实现奇数位于数组的前半部分，偶数位于数组的后半部分，其实就是不断的将偶数往后移动，从而空出对应的位置，然后将奇数插入偶数的位置，前提是要先使用中间变量保存奇数的值。同时，如果一个奇数已经确定了位置，那么后续这个奇数就不能再被交换，因为要保证奇数的位置不变。 

        代码如下。

#include<iostream>
using namespace std;void show(int *a,int num)
{for (int i = 0; i < num; i++){cout << a[i] << " ";}
}void Sort(int* a,int num)
{//保存已经排好的奇数的位置int k = 0;int j = 0;for (int i = 0; i < num; i++){//判断当前元素是否为奇数if (a[i] & 1){int tmp = a[i];j = i;//向后移动偶数数的位置while (j > k){a[j--] = a[j - 1];}//将奇数放到合适的位置a[k++] = tmp;}}}int main()
{int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };int num = sizeof(arr) / sizeof(int);show(arr,num);Sort(arr,num);cout << endl;show(arr, num);}

        运行结果如下。

        运行结果符合预期。 

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

        解析：这个题目相对简单，可以使用C++库中的uordered_map的[]特性，以为unordered_map的[],里面其实本质上就是元素的插入，如果当前元素存在就返回已经存在的元素的second，如果不存在就返回新插入的元素的second。用这一特性实现数字个数的统计。 

        代码如下。

#include <unordered_map>
class Solution {
public:int MoreThanHalfNum_Solution(vector<int>& numbers) {// write code hereunordered_map<int,int> _map;for(auto e:numbers){_map[e]++;}int length=numbers.size()/2;for(auto e:_map){//不用考虑数组长度/2之后变成小数的问题，小数在这个情境下，可以看做小数也为数组长度if(e.second>length){return e.first;}}return 0;}
};

        以上便是本期的所有内容。

        本期内容到此结束^_^