二维数组中的查找3/6：旋转数组的最小数字调整|全球快报

目录

二维数组中的查找3/6

旋转数组的最小数字

(相关资料图)

调整数组顺序

连续子数组最大和3/7

数组中的重复数字

二维数组中的查找3/6

思路：

采用右上角元素进行比较：

1 行rows = array.size();列cols = array.size(); 右上角元素下标array[0][cols - 1]

2 i 扫描行，i=0

3 当target>当前值，向下查找；i++

当target <当前值，向左查找；j--

直至找到/扫描完，退出循环

【查找】

class Solution {public:    bool Find(int target, vectorarray) {        // array是二维数组，这里没做判空操作        int rows = array.size();//行        int cols = array[0].size();//列        int i=0,j=cols-1;//右上角角元素坐标        while(i=0){//使其不超出数组范围            if(target>array[i][j])                i++;//查找的元素较小，往下找            else if(target<ARRAY[I][J]) else="" }="" return="" code="" j--;="" 查找元素较大，往左找="" true;="" 出口a，找到="" false;="" 出口b，没找到="" }};

旋转数组的最小数字

【递归】和【二分法】

二分法思路：

1 左指针l = 0，右指针r = size-1;mid = l + （r - l）/2;

2 （以下用l代称左指针指向的数字，r，mid同理）

因为原序列是非递减（含有重复数字），所以最小值可能出现在右边（不绝对，例如不旋转时候，最小值在最左边），所以这里选择mid和r进行比较。

如果mid > r,说明左边有序非递减，如{3412}或{333111}，那么最小值在右侧，要去右边的半段中找，l = mid + 1；

如果mid < r,说明右边有序非递减，如{4123}或{311133}，但是mid可能就是最小值，比如{4123}，要注意这里的边界。

特殊情况：右边非递减序列的起点可能是现在的mid，也可能在[l, mid]区间内，所以 r = mid；相当于去[l,mid]中找最小                 值，因为 此时的mid是右边最小值。

如果mid = r,出现重复元素，r--

3 当l < r 的时候一直做2的循环

跳出循环条件： l = r,这个时候l和r指向同一个元素，不用再进行比较

4 返回r指针指向的数组的值

class Solution {public:    int minNumberInRotateArray(vectorrotateArray) {        int left = 0, right = (int)rotateArray.size() - 1;        while(left < right){//注意小于号，当左右相当，即同一元素，不用比较大小            int mid = left + (right - left) / 2;            if(rotateArray[mid] > rotateArray[right]) left = mid + 1;//左半段有序，比如{3423}            else if(rotateArray[mid] < rotateArray[right]) right = mid;//右半段有序，但是mid可能就是最小值，比如{3123}，要注意这里的边界            else right--;//删除重复        }        return rotateArray[right];    }};

递归方法：

class Solution {public:    int minNumberInRotateArray(vectorrotateArray) {        if(rotateArray.empty())            return 0;        return find(rotateArray, 0, rotateArray.size()-1);    }    int find(vector&nums, int l, int r){        if(nums[l] < nums[r] || l == r)//【易错】            return nums[l];        int mid = l + (r - l) / 2;        return min(find(nums, l, mid), find(nums, mid+1, r));    }};

调整数组顺序

* 1.要想保证原有次序，则只能顺次移动或相邻交换。

* 2.i从左向右遍历，找到第一个偶数。

* 3.j从i+1开始向后找，直到找到第一个奇数。

* 4.将[i,...,j-1]的元素整体后移一位，最后将找到的奇数放入i位置，然后i++。

* 5.終止條件：j向後遍歷查找失敗。

*/

【插入排序】

插入排序类似于打扑克，新拿的牌A放在最后，然后向前扫描，遇到比A大的B，则AB交换位置

本题是奇数在前，偶数在后，要求保证顺序不变，那么相当于偶数A在最前面，然后向后扫描，遇到奇数B，两者交换位置

插入排序思路：（更快一点）

1 i 从前往后扫描，找到第一个偶数A

2 j = i + 1，从前往后扫描，找到第一个奇数B

3 将[i,...,j-1]的元素整体后移一位，最后将找到的奇数B放入i位置。

4 i++， j = i + 1；继续循环

5 跳出循环条件： j到达结尾

class Solution {public:    void reOrderArray(vector&array) {        for(int i = 0; i < array.size(); i++){            if(array[i] % 2 == 0){//找到第一个偶数                for(int j = i; j < array.size(); j++){                    if(array[j] % 2 == 1){//找到最后位置上的奇数                        int temp = array[j];                        for(; j > i;j--){                            array[j] = array[j-1];//【i,j-1】位置向后移动一位                        }                        array[i] = temp;//偶数位置i上填上奇数array[j]                        i++;//【易错】偶数指针向后移（下标，不是实际意义上的指针）                    }                }            }        }    }};

冒泡排序

左和右只要是奇数偶数就要交换，把奇数向前

如果左右都是奇数/偶数，则不交换

class Solution {public:    void reOrderArray(vector&array) {                  for (int i = 0; i < array.size();i++)        {            for (int j = array.size() - 1; j>i;j--)            {                if (array[j] % 2 == 1 && array[j - 1]%2 == 0) //前偶后奇交换                {                    swap(array[j], array[j-1]);                }            }        }    }};

新建数组的思路：

1 从前往后扫描，遇到奇数，压入数组A

2从后往前扫描，遇到偶数，压入数组A

3 数组A赋值给array

class Solution {public:    void reOrderArray(vector&array) {        vectorres;        for(int i = 0; i < array.size(); ++i){            if((array[i] & 1) != 0)                res.push_back(array[i]);        }        for(int i = 0; i < array.size(); ++i){            if((array[i] & 1) == 0)                res.push_back(array[i]);        }        array = res;    }};

插入排序方法更快一点

数组中出现次数超过一半的数

“对数组进行排序，如果有一个数字出现的次数超过数组长度的一半，那么这个元素一定是数组长度/2索引位置的那个元素，再遍历数组，统计出现的次数是否大于一半即可。”

我还想到哈希表映射，但是哈希表必然最慢。

中间元素思路：

1，数组排序，sort

2，取中间元素array[(size - 1) / 2],记作A

3，扫描数组，计算A出现次数

class Solution {public:    int MoreThanHalfNum_Solution(vectornumbers) {    //数组排序        sort(numbers.begin(),numbers.end());        //取中间元素值        int mid = numbers[(numbers.size() - 1) / 2];        //遍历得出中间元素出现次数        int cnt = 0;//【易错】我竟然没给cnt初始化        for(int i = 0; i < numbers.size(); i++){            if(mid == numbers[i])                cnt++;        }        if(cnt > numbers.size() / 2)             return mid;        else            return 0;    }};

哈希表hashmap

class Solution {public:    int MoreThanHalfNum_Solution(vectornumbers) {        for (int i = 0; i < numbers.size(); i++) {            hash_map[numbers[i]] += 1;//遍历数组，将数组元素压入哈希表，没出现一次，计数加一        }//【我不会写哈希表哭哭】【我现在会了】                for (int i = 0; i < numbers.size(); i++) {            if (hash_map[numbers[i]] > (numbers.size() / 2)) {                  return numbers[i];            }        }        return 0;    }private:    maphash_map;};

解决问题提交时间状态运行时间占用内存使用语言

数组中出现次数超过一半的数字（哈希表）2020-03-07答案正确4 ms480KC++

数组中出现次数超过一半的数字（计数法）2020-03-07答案正确3 ms456KC++

数组中出现次数超过一半的数字（有序数组中间位置元素）2020-03-07答案正确2 ms584KC++

连续子数组最大和3/7

构建乘积数组

"考虑将A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]分成左右两部分求解，其中C[i] = A[0]*A[1]*...*A[i-1]，D[i] = A[i+1]*...*A[n-1]，那么B[i] = C[i] * D[i]。实际上C[i] = C[i-1] * A[i-1]而D[i] = D[i+1] * A[i+1]。

我们可以先遍历一遍A，求的D，然后再利用B[i] = C[i] * D[i]，求出B[i]，而C[i] = C[i-1] * A[i-1]，不再需要循环求解，每次乘上A[i-1]即可。"

思路：

正方形矩阵，对角线不能参与乘积。矩阵被分为左下角和右上角。

对于每一行都可理解为B[i] = 左[i] * 右[i]

1 遍历计算右边，如果从上到下计算：i从1 到 size-1，i++：右[i] =右[i - 1] *A[i - 1]

可以从下往上计算：i从size - 2 到0，i--：右[i] = 右[i + 1] * A[i + 1]

注：右[最底下那一行] = 1;

2 因为B[i] = 左[i] * 右[i]，

已知左[0] = 1, 所以B[0] = 1 * 右[0]

左[1] = 左[0] * A[0], 所以B[1] = 左[1] * 右[1] = A[0] * 右[1]

左[2] = 左[1] * A[1], 所以B[2] = 左[2] * 右[2] = A[0] *A[1] * 右[1]

因此 左[i] = 左[i -1] * A[i - 1]

【边界条件的处理】

class Solution {public:    vectormultiply(const vector& A) {            int length = A.size();        vectorres(A.size(), 1);//数组大小为A的size，数组初始化为1                for(int i = length - 2; i >= 0; i--){            res[i] = res[i + 1]* A[i+1];//从下往上计算右边乘积            //注res[length - 1] = 1,已经在初始化阶段写好了        }                int temp = 1;//temp保存左边乘积，当i=0时，左边 = 1        //随着i递增，左边[i] = 左边[i-1]*A[i-1]        for(int i = 0; i < length; i++){            res[i] = temp * res[i];//算总乘积            temp *= temp * A[i];//算左边的乘积        }        return res;    }};

数组中的重复数字

数据结构里面有个哈希表的表排序->重要结论：N个数字的排列是由若干个独立的环组成的。

想要排序就要swap，swap之后形成环，当有重复元素时候无法成环；

本题利用的就是这个思想。

思路：

1 从前往后扫描，扫描第i个元素时，元素下标i，值记作A[i] = B。

2 如果 i = B，i++，扫描下一位（环中只有一个元素）

如果 i 不等于B，找到以B为下标的值：A[B]

3 比较B 和 A[B]，如果相等，出现重复元素；

如果不相等，交换二者位置（交换后，B的值放在了下标为B的地方，A[B] = B）。

直至遍历结束.

没找到重复元素，返回false

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) {        if(length <= 1) return false;        for(int i = 0; i < length; ++i){            while(i != numbers[i]){                if(numbers[i] == numbers[numbers[i]]){                   *duplication = numbers[i];                    return true;                }                else                    swap(numbers[i],numbers[numbers[i]]);            }        }        return false;    }};

思路：数组里数字的范围保证在0 ~ n-1 之间，所以可以利用现有数组设置标志，

当访问一个元素，将元素值+length。

访问之前要先判断元素值是否>=length，大于等于则被访问过，要剪掉length才能拿到原本的元素内容 赋值给*duplication

小于则没被访问过，将元素值+length。

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) {        for(int i=0;i!=length;++i){//扫描数组        int index=numbers[i]%length;//如果index大于length说明被访问过，要剪掉length才能等于原来的num[i]            //如果index小于length 则不用取余            //if(index >= length)//与上一句意思一样的              //  index -= length;        if(numbers[index]>=length){            *duplication=index;//被访问过            return 1;        }                      numbers[index]+=length;      }    return 0;    }};