目录

1.二维数组中的查找

2.旋转数组的最小数字

3.调整数组顺序使奇数位于偶数前面

4.数组中出现次数超过一半的数字

---

1.二维数组中的查找

核心考点：数组相关，特性观察，时间复杂度的把握

【描述】

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

[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]

给定 target = 7，返回 true。
给定 target = 3，返回 false。
进阶：空间复杂度 O(1) ，时间复杂度 O(n+m)

方法一：遍历整个数组看是否有这个数字，有返回true，没有返回false。

class Solution {
public:bool Find(int target, vector<vector<int> > array) {for(int i=0;i<array.size();++i){for(int j=0;j<array[0].size();++j){if(target==array[i][j])return true;}}return false;}
};

正常查找的过程，本质就是排除的过程，如果双循环查找，一次排除一个，效率太低。

方法二：找一个基准值，这个基准值有两个左下角或右上角。以右上角为例，已知题中给出每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，那么右上角这个数是第一行最大，最后一列的最小。想要查找的数字比基准值小，排除最后一列，这一列没有比基准值还小的数，列--；查找的数字比基准值大，这一行没有比基准值还大的数，行++；如果找到返回true。当遍历完整个数组没有找到，返回false。这样可以一次排除一行或一列。

左下角：从左下角开始，比左下角大，列--；比左下角小，行--。

class Solution {
public:bool Find(int target, vector<vector<int> > array) {//右上角的值int i=0;int j=array[0].size()-1;while(i<=array.size()-1&&j>=0){if(target>array[i][j]){++i;}else if(target<array[i][j]){--j;}elsereturn true;}return false;//左下角的值
//         int i=array.size()-1;
//         int j=0;//         while(i>=0 && j<array[0].size())
//         {
//             if(target<array[i][j])
//             {
//                 i--;
//             }
//             else if(target>array[i][j])
//             {
//                 j++;
//             }
//             else
//             {
//                 return true;
//             }
//         }
//         return false;
//     }
//         }
};

2.旋转数组的最小数字

数组理解，二分查找，临界条件

原题链接

【描述】

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

输入：[3,4,5,1,2]

返回值：1

要求：空间复杂度：O(1) ，时间复杂度：O(logn)

【算法思想】：

这道题的思路可以借鉴二分法，这里数组旋转可以将数组看作两部分，前半部分整体非递减（递增或相等），后半部分整体非递减，前半部分整体大于等于后半部分。

所以，我们可以定义最左值下标left，最右值下标right，中间值下标mid(左右下标相加除以2)，当中间值大于left值，说明最小值在右半部分，更新区间，将mid下标赋给left；如果中间值小于left值，说明左边有比中间值还小的值，或者这个最小值就是他自己，因为右边值都比都比mid值要大，更新区间，将mid下标赋给right。

我们先写大框：

class Solution {
public:int minNumberInRotateArray(vector<int> rotateArray) {int left=0;int right=rotateArray.size()-1;int mid=(left+right)>>1;while(left<right){if(rotateArray[mid]>=rotateArray[left]){left=mid;}else{right=mid;}}return rotateArray[mid];
}

 考虑到两种情况：

• 数组为空，没有数据
• 左中右三个数相等

lass Solution {
public:int minNumberInRotateArray(vector<int> rotateArray) {//数组为空，直接返回if(rotateArray.empty()){return 0;}//设定左中右值下标int left=0;int right=rotateArray.size()-1;int mid=(left+right)>>1;//当左中右三数相等，缩小范围，在[left+1,right-1]中比较        if(rotateArray[left]==rotateArray[mid]&&rotateArray[mid]==rotateArray[right]){int result=rotateArray[left];for(int i=left+1;i<right;++i){if(result>rotateArray[i]){result=rotateArray[i];}}return result;}if(rotateArray[left]<rotateArray[right]){return rotateArray[left];}while(left<right){if(right-left==1){mid=right;break;}if(rotateArray[mid]>=rotateArray[left]){left=mid;}else//rotateArray[mid]<rotateArray[left]{right=mid;}mid=(left+right)>>1;}return rotateArray[mid];}
};

3.调整数组顺序使奇数位于偶数前面

核心考点：数组操作，排序思想的扩展使用

原题链接

【描述】：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

【思路】：
左边遇到的偶数和右边遇到的奇数交换，这样奇数就全在左边，偶数就全在右边。

#include <stdio.h>void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}void reSort(int a[], int num)
{int left = 0;int right = num - 1;while (left<right){//找偶数，遇到奇数++while (left<right && a[left] & 1){++left;}//找奇数，遇到偶数--while (left<right && !(a[right] & 1)){--right;}Swap(&a[left], &a[right]);}
}void PrintArr(int a[],int n)
{for (int i = 0; i < n; ++i){printf("%d ", a[i]);}printf("\n");
}int main()
{int arr[] = { 3, 2, 4, 5, 1, 2, 4 };reSort(arr, sizeof(arr) / sizeof(int));PrintArr(arr,sizeof(arr)/sizeof(int));
}

当我们加再上一个条件，保证奇数和奇数，偶数和偶数之间的相对位置不变

【思路】：遇到奇数，将奇数保存下来，前面的偶数向后移动，直到遇到前一个奇数。这里我们用一个下标k来保存奇数存放位置，存放一个奇数k++,这样当偶数移动到大于k的时候就不再移动，k的位置放保存下来的奇数。

class Solution {
public:void reOrderArray(vector<int> &array) {int k=0;//标识已经放好位置的奇数的下标for(int i=0;i<array.size();++i){if(array[i]&1)//奇数{int odd=array[i];int j=i;//用j保存i当前位置，直接用i的话，后面的i也会被改变while(j>k)//等于k的时候已经遍历到以最后一个偶数{array[j]=array[j-1];--j;}array[k]=odd;k++;}}}
};

这段代码我们在想第一个奇数怎么办，当用j保存i当前位置，i和k的下标都是0，也就是说这个数组里面还没有排好的奇数，j不会大于k，所以直接将保存好的奇数放到所在位置。这里代码可以优化一下，小伙伴们努力一下咯。

4.数组中出现次数超过一半的数字

 核心考点: 数组使用，简单算法的设计

原题链接

【描述】：

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

要求：空间复杂度：O(1)，时间复杂度 O(n)

          保证数组输入非空，且保证有解

输入：[1,2,3,2,2,2,5,4,2]

返回值：2

【思路】：

如果数字超过整个数组的一半，，那么它遇到不相同的数字就相消，遇到相同的数字++，这样最后剩下的一定是超过一半的数字。

class Solution {
public:int MoreThanHalfNum_Solution(vector<int> numbers) {//先找出现最多的数字int num=numbers[0]; int count=1;//记录数字出现次数for(int i=1;i<numbers.size();++i){//遇到相同+1，不相同-1if(num==numbers[i]){count++;}else{count--;}//如果等于0，更新num数字，并将count置1if(count==0){num=numbers[i];count=1;}}//判断数字是否过半//遍历整个数组，计数这个数字是否超过一半int countNum=0;for(int i=0;i<numbers.size();++i){if(num==numbers[i]){countNum++;}}int half=numbers.size()>>1;if(countNum>half){return num;}elsereturn 0;}
};