一, 数组
1. 二维数组中的查找
题目描述:
? 在一个二维数组中 (每个一维数组的长度相同), 每一行都按照从左到右递增的顺序排序, 每一列都按照从上到下递增的顺序排序. 请完成一个函数, 输入这样的一个二维数组和一个整数, 判断数组中是否含有该整数.
思路: 二分查找
? 遍历每一行, 对每一行进行一次二分查找. 时间复杂度 O(nlogn), 空间复杂度 O(1)
代码:
- class Solution {
- public:
- bool Find(int target, vector<vector<int>> array) {
- for(int i=0;i<array.size();i++){
- int low=0;
- int high=array[i].size()-1;
- while(low<=high){
- int mid=(low+high)/2;
- if(target<array[i][mid]){
- high=mid-1;
- }else if(target>array[i][mid]){
- low=mid+1;
- }else{
- return true;
- }
- }
- }
- return false;
- }
- };
2. 数组中重复的数字
题目描述:
? 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内. 数组中某些数字是重复的, 但不知道有几个数字是重复的. 也不知道每个数字重复几次. 请找出数组中任意一个重复的数字. 例如, 如果输入长度为 7 的数组 {2,3,1,0,2,5,3}, 那么对应的输出是第一个重复的数字 2.
思路: 哈希
? 时间复杂度 O(n), 空间复杂度 O(n)
代码:
- class Solution {
- 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 false
- bool duplicate(int numbers[], int length, int* duplication) {
- int hashTable[length];
- for(int i=0;i<length;i++){
- hashTable[i]=0;
- }
- for(int i=0;i<length;i++){
- hashTable[numbers[i]]+=1;
- if(hashTable[numbers[i]]>1){
- *duplication=numbers[i];
- return true;
- }
- }
- return false;
- }
- };
[注意] 使用变量定义数组长度时, 不要在定义的同时进行初始化赋值, 要在之后进行赋值.
? 即上面在开哈希数组的时候, 不要写成 int hashTable[length]={0};
3. 构建乘积数组
题目描述:
? 给定一个数组 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[i] 的值分成左右两部分来计算, 先算 A[0]*A[1]...A[i-1] 的值, 再算 A[i+1]A[i+2]...A[n-1] 的值, 最后把左右两部分乘起来就是 B[i] 的值了.
左边: 右边:
- L[0]=1; R[0]=A[1] * A[2] ... A[n-2] * A[n-1]=R[1] * A[1];
- L[1]=A[0]=L[0] * A[0]; ......
- L[2]=A[0] * A[1]=L[1] * A[1]; R[n-3]=A[n-2] * A[n-1]=R[n-2] * A[n-2];
- ...... R[n-2]=A[n-1]=R[n-1] * A[n-1];
- L[n-1]=A[0] * A[1] ... A[n-2]=L[n-2] * A[n-2]; R[n-1]=1;
时间复杂度 O(n), 空间复杂度 O(n)
代码:
- class Solution {
- public:
- vector<int> multiply(const vector<int>& A) {
- int n=A.size();
- vector<int> L(n);
- L[0]=1;
- for(int i=1;i<n;i++){
- L[i]=L[i-1]*A[i-1];
- }
- vector<int> R(n);
- R[n-1]=1;
- for(int i=n-2;i>=0;i--){
- R[i]=R[i+1]*A[i+1];
- }
- vector<int> B(n);
- for(int i=0;i<n;i++){
- B[i]=L[i]*R[i];
- }
- return B;
- }
- };
来源: http://www.bubuko.com/infodetail-3421500.html