《剑指offer》：数组部分

墨蓝 2023-07-04 15:51 100阅读 0赞

**一、数组中重复的数字**

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

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

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(numbers==NULL||length==0)
                return false;
            //定义并遍历哈希表
            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];
                    return true;
                }
            }
            return false;
        }
    };

**二、二维数组中的查找**

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

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

#方法一：从左下角开始遍历
    class Solution {
    public:
        bool Find(int target, vector<vector<int> > array) {
            //判空操作
            if(array.empty())
                return false;
            int row=array.size()-1; //行遍历
            int column=0;
            while(row>=0&&column<array[0].size())
            {
                if(array[row][column]==target)
                    return true;
                else if(array[row][column]>target)
                {
                    row--;
                }
                else
                    column++;
            }
            return false;
        }
    };
    #方法二：从右上角开始遍历
    class Solution {
    public:
        bool Find(int target, vector<vector<int> > array) {
            if(array.empty())
                return 0;
            int row=0;
            int col=array[0].size()-1;
            while(col>=0&&row<array.size())
            {
                if(target==array[row][col])
                    return 1;
                else if(target<array[row][col])
                    col--;
                else
                    row++;
            }
            return 0;
        }
    };

**三、构建乘积数组**

**题目：**给定一个数组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\])两部分分别求解，先对右半部分乘，再对左半部分乘。

class Solution {
    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;
        }
    };

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

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

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

class Solution {
    public:
        void reOrderArray(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\}），这时候只能靠直接遍历了**

class Solution {
    public:
        int minNumberInRotateArray(vector<int> rotateArray) {
            //判空操作
            if(rotateArray.empty())
                return 0;
            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;
                else if(rotateArray[mid]>=rotateArray[left])
                    left=mid;
                if(rotateArray[left]==rotateArray[mid]&&rotateArray[left]==rotateArray[right])
                    return ByOrder(rotateArray,left,right);
            }
            if(left>=right)
                return 0;
            return rotateArray[mid];
        }
        int ByOrder(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;
        }
    };

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

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

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

class Solution {
    public:
        void reOrderArray(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;
        }
    };

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

class Solution {
    public:
        void reOrderArray(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度

**解题思路**：找到替换公式，本题迎刃而解。即![matrix\[i\]\[j\]=matrix\[j\]\[n-i-1\]][matrix_i_j_matrix_j_n-i-1]

//方法一：时间复杂度和空间复杂度皆为O(n^2)
    class Solution {
    public:
        void rotate(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;
        }
    };
    //方法二：节省空间复杂度的办法
    class Solution {
    public:
        void rotate(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;
                }
            }
        }
    };

**反思：**

*  水平翻转：![matrix\[i\]\[j\]=matrix\[n-i-1\]\[j\]][matrix_i_j_matrix_n-i-1_j]
 *  主对角线翻转：![matrix\[i\]\[j\]=matrix\[j\]\[i\]][matrix_i_j_matrix_j_i]

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

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

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

*  首先，从头到尾遍历，遍历出来不相同的数字
 *  然后通过位运算便利出来第二个出现了一次的数字
 *  最后找出来第一个出现了一次的数字

class Solution {
    public:
        void FindNumsAppearOnce(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];
            }
        }
    };

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

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

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

class Solution {
    public:
        int GetNumberOfK(vector<int> data ,int k) {
            int start,end,mid,count=0,i;
            unsigned int len = data.size();
            if(!len)
                return 0;
            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;
        }
    };

[O_n_2]: https://private.codecogs.com/gif.latex?O%28n%5E%7B2%7D%29
[matrix_i_j_matrix_j_n-i-1]: https://private.codecogs.com/gif.latex?matrix%5Bi%5D%5Bj%5D%3Dmatrix%5Bj%5D%5Bn-i-1%5D
[matrix_i_j_matrix_n-i-1_j]: https://private.codecogs.com/gif.latex?matrix%5Bi%5D%5Bj%5D%3Dmatrix%5Bn-i-1%5D%5Bj%5D
[matrix_i_j_matrix_j_i]: https://private.codecogs.com/gif.latex?matrix%5Bi%5D%5Bj%5D%3Dmatrix%5Bj%5D%5Bi%5D