《剑指offer》：数组部分

一、数组中重复的数字

题目描述：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

解题思路：考虑用哈希表进行操作。第一遍遍历整个数组更新哈希表值，第二遍遍历哈希表中对应元素值大于1的元素，输出该元素即为待查找元素。

classSolution {
public:// Parameters://        numbers:     an array of integers//        length:      the length of array numbers//        duplication: (Output) the duplicated number in the array number// Return value:       true if the input is valid, and there are some duplications in the array number//                     otherwise falseboolduplicate(int numbers[], int length, int* duplication){//判空操作if(numbers==NULL||length==0)returnfalse;//定义并遍历哈希表int hashpub[7]={0};for(int i=0;i<length;i++){hashpub[numbers[i]]++;}for(int j=0;j<length;j++){if(hashpub[numbers[j]]>1){duplication[0]=numbers[j];returntrue;}}returnfalse;}
};

二、二维数组中的查找

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

解题思路：本题可以从左下角或者右上角两个方向进行搜索，以从左下角搜索为例，若左下角的数字小于待查找数字，则应该继续往该行右侧查找；若左下角的数字大于待查找数字，则应该从上面的行查找。

#方法一：从左下角开始遍历
classSolution {
public:boolFind(int target, vector<vector<int> > array){//判空操作if(array.empty())returnfalse;int row=array.size()-1; //行遍历int column=0;while(row>=0&&column<array[0].size()){if(array[row][column]==target)returntrue;elseif(array[row][column]>target){row--;}elsecolumn++;}returnfalse;}
};
#方法二：从右上角开始遍历
classSolution {
public:boolFind(int target, vector<vector<int> > array){if(array.empty())return0;int row=0;int col=array[0].size()-1;while(col>=0&&row<array.size()){if(target==array[row][col])return1;elseif(target<array[row][col])col--;elserow++;}return0;}
};

三、构建乘积数组

题目：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）

解题思路：这里可以考虑B[j]=(A[0]*...*A[j-1])*(A[j+1]*...*A[n-1])两部分分别求解，先对右半部分乘，再对左半部分乘。

classSolution {
public:vector<int> multiply(const vector<int>& A){int n=A.size();vector<int>B(n);int ret=1;//求右边for(int i=0;i<n;ret*=A[i++]){B[i]=ret;}ret=1;for(int j=n-1;j>=0;ret*=A[j--]){B[j]*=ret;}return B;}
};

四、调整数组顺序使奇数位于偶数前面

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

解题思路：本题要求不仅仅是奇数部分位于前半部分，还有偶数部分位于后半部分，要想保证相对位置不变，就不能单纯通过穷举遍历来进行交换，因此在这里我用冒泡排序来解决，时间复杂度是

编辑。

classSolution {
public:voidreOrderArray(vector<int> &array){//使用冒泡排序for(int i=0;i<array.size();i++)  //外层控制趟数for(int j=array.size()-1;j>i;j--)if(array[j]%2!=0&&array[j-1]%2==0){int tmp=array[j];array[j]=array[j-1];array[j-1]=tmp;}}
};

五、旋转数组的最小数字（考点：查找）

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路：本题可以考虑使用顺序查找的方法，时间复杂度为o(n)。同时，亦可以考虑使用二分查找的思路，由题目可以知后面部分总比前面部分小，那么只要将中间元素和左右两边进行对比，就可以知道最小值是在哪一边了，然后循环使用这种方法，最终只要right和left相邻，则right值即为最小值位置。

注意：在《剑指offer》中指出了两种我们需要考虑的情况

1、若排序数组的前面0个数字跑到最后面（即数组没变化），那么这时候第一个元素就是最小值，不用进行这么多遍历了

2、如果存在只挪动了1个元素的数组（如：{0,1,1,1}->{1,0,1,1}），这时候只能靠直接遍历了

classSolution {
public:intminNumberInRotateArray(vector<int> rotateArray){//判空操作if(rotateArray.empty())return0;int left=0,right=rotateArray.size()-1,mid=left;while(rotateArray[left]>=rotateArray[right]){mid=(left+right)/2;if(right-left==1){mid=right;break;}if(rotateArray[mid]<=rotateArray[right])right=mid;elseif(rotateArray[mid]>=rotateArray[left])left=mid;if(rotateArray[left]==rotateArray[mid]&&rotateArray[left]==rotateArray[right])returnByOrder(rotateArray,left,right);}if(left>=right)return0;return rotateArray[mid];}intByOrder(vector<int>a,int l,int r){int min=a[l];for(int i=l;i<=r;i++)if(a[i]<min){min=a[i];}return min;}
};

六、调整数组顺序使奇数位于偶数前面

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

解题思路：两次遍历，第一次遍历只保存奇数的数，第二次保存在第一次的基础上，只是这次保留的是偶数。

classSolution {
public:voidreOrderArray(vector<int> &array){int size=array.size();if(size==0) return;vector<int>res;for(int i=0;i<size;i++){if(array[i]%2!=0)res.push_back(array[i]);}for(int i=0;i<size;i++){if(array[i]%2==0)res.push_back(array[i]);}array=res;}
};

反思：如果题目没有相对位置不变的要求？那么考虑使用快慢指针，头指针遍历前面的，尾指针遍历后面的，头指针遍历到偶数就和尾指针交换值，尾指针遍历到奇数就和头指针交换值。

classSolution {
public:voidreOrderArray(vector<int> &array){int size=array.size();if(size==0) return;int begin=0,end=size-1;while(begin<end){while(begin<end&&array[begin]%2!=0)begin++;while(begin<end&&array[end]%2==0)end--;//交换if(begin<end){int tmp=array[begin];array[begin]=array[end];array[end]=tmp;}}}
};

七、旋转矩阵

题目要求：实现矩阵顺时针旋转90度

解题思路：找到替换公式，本题迎刃而解。即

编辑

//方法一：时间复杂度和空间复杂度皆为O(n^2)classSolution {
public:voidrotate(vector<vector<int>>& matrix){int n = matrix.size();// C++ 这里的 = 拷贝是值拷贝，会得到一个新的数组auto matrix_new = matrix;for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {matrix_new[j][n - i - 1] = matrix[i][j];}}// 这里也是值拷贝matrix = matrix_new;}
};
//方法二：节省空间复杂度的办法classSolution {
public:voidrotate(vector<vector<int>>& matrix){int n = matrix.size();for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < (n + 1) / 2; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[n - j - 1][i];matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];matrix[j][n - i - 1] = temp;}}}
};

反思：

水平翻转：

编辑

主对角线翻转：

八、数组中只出现一次的数字

题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

解题思路：本题考查了异或操作。

• 首先，从头到尾遍历，遍历出来不相同的数字

• 然后通过位运算便利出来第二个出现了一次的数字

• 最后找出来第一个出现了一次的数字

classSolution {
public:voidFindNumsAppearOnce(vector<int> data,int* num1,int *num2){int len=data.size();if(len<2) return;int counter=0;//先从头到尾遍历，遍历出来不同的数字for(int i=0;i<len;i++)counter=data[i]^counter;int flag=1;while(flag){if(flag&counter)break;flag=flag<<1; //逐个遍历}for(int i=0;i<len;i++){if((data[i]&flag)) *num1=*num1^data[i];else *num2=*num2^data[i];}}
};

九、数字在排序数组中出现的次数

题目描述:统计一数字在排序数组中出现的次数。

解题思路：使用两次遍历的方法，第一次使用二人查找，把相同的末位元素遍历出来；第二遍在数相同的有多少个。

classSolution {
public:intGetNumberOfK(vector<int> data ,int k){int start,end,mid,count=0,i;unsignedint len = data.size();if(!len)return0;start =0;end = len-1;mid = start;while(start<end){mid = (start+end)/2;if(k >data[mid])start = mid+1;if(k<data[mid])end = mid-1;if(k==data[mid])break;}i=mid;while( (i>=0) && (k==data[i])){i--;count++;}i=mid+1;while((i<len)&& (k==data[i]) ){i++;count++;}return count;}
};

十、剑指 Offer II 001. 整数除法（力扣）

题目描述:给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

解题思路：使用减法代替除法。

classSolution {publicintdivide(int a, int b) {if(a==Integer.MIN_VALUE&&b==-1)return Integer.MAX_VALUE;int sign=((a>0)^(b>0))?-1:1;if(a>0)a=-a;if(b>0)b=-b;int res=0;while(a<=b){a-=b;res++;}return sign==1?res:-res;}
}