练题100天——DAY21：统计奇数个数+合并有序数组-CSDN博客

今天写了两道题，难度★~★★★，并更新了之前的DAY13的冒泡排序+二进制求和、DAY14全排列的思路

更新于25/12/8：增加了合并两个有序数组中的官方题解

一.在区间范围内统计奇数个数 ★☆☆☆☆

题目

力扣1523. 在区间范围内统计奇数数目：给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。

思路

直接利用循环，遍历从low到high之间的数字，统计奇数的个数.

注意：这种做法有超时的风险。

代码

class Solution {
public:
    int countOdds(int low, int high) {
        int count=0;
        for(int i=low;i<=high;i++){
            if(i%2!=0){
                count++;
            }
        }
        return count;
    }
};

时间复杂度

O(n)：n表示区间长度high-low+1

官方题解

思路

利用前缀和的思路，用pre(x)表示0~x的奇数个数，则pre(x)=⌊(x+1)/2⌋(向下取整)。因为数字都是就排列的，0~x一共 x+1 个数，那么奇数和偶数“各占一半”，同时x为偶数时，总体的偶数比奇数多一个。所以这道题可以直接用 pre(high)-pre(low-1)得出结果。

注意：因为题目中要求包含low和high，所以是pre(high)-pre(low-1)，如果用pre(high)-pre(low)会导致漏掉low本身

代码

我直接返回的表达式，官方将pre写成了一个函数

class Solution {
public:
    int countOdds(int low, int high) {
        return ((high+1)/2)-((low)/2);
    }
};

时间复杂度

O(1)：与输入规模无关的常规操作

二.合并两个有序数组 ★★★☆☆

题目

88. 合并两个有序数组给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

思路

先将nums1的元素保存到新数组nums中，然后比较nums和nums2的元素，大的放入nums1，同时对应的索引要移动。最后按照题目要求格式打印nums1即可。

代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        //双指针
        //较小的值放入nums1
        //先将nums的元素保存到另一个数组中
        vector<int> nums(m);
        for(int i=0;i<m;i++){
            nums[i]=nums1[i];
        }
        int i=0,j=0,index=0;
        while(i<m && j<n){
            if(nums[i]>nums2[j]){
                nums1[index++]=nums2[j++];
            }else{
                nums1[index++]=nums[i++];
            }
        }
        //循环结束可能只有一个数组的元素被全部保存
        if(index!=m+n){
            while(i<m){
                nums1[index++]=nums[i++];
            }
            while(j<n){
                nums1[index++]=nums2[j++];
            }
        }

        printf("[");
        for(i=0;i<m+n;i++){
            if(i==m+n-1){
                printf("%d",nums1[i]);
            }else{
                printf("%d,",nums1[i]);
            }
        }
        printf("]");
    }
};

时间复杂度

O(m+n)

官方题解

方法1——合并后排序

先将nums2中元素放到nums1数组的后面，然后用sort排序即可

代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i=m,j=0;i<m+n;i++,j++){
            nums1[i]=nums2[j];
        }
        sort(nums1.begin(),nums1.end());
    }
};

复杂度

时间复杂度：O((m+n)log(m+n))

空间复杂度：O(log(m+n))

方法2——双指针

利用p1、p2两个“指针”分别指向nums1和nums2的元素，比较后将较小的放入临时数组res中。res的长度为m+n。

while条件设为 p1<m || p2<n，可以使得元素的赋值均在while循环内实现。当p1<m 且 p2<n时，说明两个数组的元素都没完全放入res中，所以进行比较，将较小的放入即可。当p1==m时，说明nums1的元素已完全放入，此时只需要将nums2中剩余元素放入即可。当p2==n时同理。

代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1=0;
        int p2=0;
        int res[m+n];//可以直接用一般数组的常见方式
        int temp=0;
        while(p1<m || p2<n){
            if(p1==m){
                temp=nums2[p2++];
            }else if(p2==n){
                temp=nums1[p1++];
            }else if(nums1[p1]<nums2[p2]){
                temp=nums1[p1++];
            }else{
                temp=nums2[p2++];
            }
            res[p1+p2-1]=temp;
        }
        for(int i=0;i < m+n;i++){
            nums1[i]=res[i];
        }
    }
};

复杂度

时间复杂度：O(m+n)——循环m+n次

空间复杂度：O(m+n)——因为需要额外创建一个长度m+n的数组

方法3——逆向双指针

这个方法与方法2不同的是，没有额外创建数组，而是选择从nums1的空闲位置开始赋值。

用p1、p2分别指向nums1和nums2的最后一个数字，index表示放入元素的指针，temp保存当前要放入的元素。同样地，while条件设为 p1>=0 || p2>=0，使得元素的赋值均在while循环内实现。当p1>=0 且 p2>=0时，说明两个数组的元素都没完全按要求放入，所以进行比较，将较大的放入index所指位置即可。当p1==-1时，说明nums1的元素已完全按要求放入，此时只需要将nums2中剩余元素放入即可。当p2==-1时同理。

代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1=m-1;
        int p2=n-1;
        int index=m+n-1;
        int temp=0;
        while(p1>=0 || p2>=0){
            if(p1==-1){
                temp=nums2[p2--];
            }else if(p2==-1){
                temp=nums1[p1--];
            }else if(nums1[p1]>=nums2[p2]){
                temp=nums1[p1--];
            }else{
                temp=nums2[p2--];
            }
            nums1[index--]=temp;
        }
    }
};