NC636牛牛爱奇数
一.题目描述
对于一个序列,每一次操作可以把相同的偶数除以2,求将整个序列全部变成奇数最少需要几次操作。
图片说明
解释:对所有的2进行一次操作数组变为[1,1,3],那么满足整个序列全部变成奇数
二.算法(模拟)
首先理解题意我们知道对于相同的偶数而言,我们每一次的操作是相同的那么,那么对于每一个偶数我们来记录其是否被操作过,并且记录下经过几次操作后,偶数可以变成奇数。但是我们需要注意对于每一次处理前后的数都要进行标记,这样的话再遍历过程中遇到前面被操作过的数就直接跳过,下面是完整代码加注释:

class Solution {
public:
    int oddNumber(int n, vector<int>& a) {
        int len=a.size();//数列的长度
        int cn=0;
        map<int,int>mp;//用来标记数在前面有没有被操作过
        for(int i=0;i<len;i++){
            if(a[i]%2==0&&a[i]!=0){//这块感觉加一个!=0会保险一点
                int num=a[i];
                //对于没有标记的数 就记录其变为奇数的次数
                while(num%2==0&&!mp[num]){
                    mp[num]++;//记录次数
                    num/=2;
                    cn++;
                }
            }
        }
        //返回最少操作次数
        return cn;
    }
};

时间复杂度:对整个序列进行遍历,对于偶数不断进行除以2的操作,所以时间复杂度是
空间复杂度:需要额外的空间对相同偶数需要次数的记录
三.算法(set)
我们可以利用STL中的set来解决,下面对set做一个简单介绍:

//对于集合我们都很了解,具有排异性,并没有相同元素,在set中也遵循这条规矩。 
//而且在set中,存在系统自动排序的操作,也就是set可以对所有插入的元素进行去重和自动排序。
/*
insert(x)      向容器类插入一个元素x
begin()       返回set容器的第一个元素的地址
end()      返回set容器的最后一个元素的下一个元素地址 所以最后一个元素是--end()
clear()      删除set容器中的所有的元素
empty()     判断set容器是否为空
max_size()    返回set容器可能包含的元素最大个数
size()      返回当前set容器中的元素个数
erase(it)       删除迭代器指针it处元素
*/

利用STL中的set,首先将所有数中的偶数插入set中。由于set会对所有插入的数进行排序,取出当前最后的一位数就是此时的最大偶数,如果将最大的数除以2之后还是一个偶数,则将最大偶数除以2之后的插入set,删除当前最大偶数,对于每一次的操作计数器加一,最后返回计数结果。
图片说明
下面是完整代码:

class Solution {
public:
    int oddNumber(int n, vector<int>& a) {
        set<int>st;
        for(int i=0;i<n;i++){
            if(a[i]%2==0){//将所有的偶数插入
                st.insert(a[i]);
            }
        }
        int ans=0;//计数器
        while(st.size()){
            //set自动对所有元素进行排序
            //--st.end()才是最后一个元素的地址
            int mx=*(--st.end());
            if((mx/2)%2==0){
                //要是除以2以后还是偶数就继续插入
                st.insert(mx/2);
            }
            //删除最后一个元素--st.end()本身就表示的是最后一个元素的地址
            st.erase(--st.end());
            ans++;//计数器加一
        }
        //返回ans
        return ans;
    }
};

时间复杂度:最多会处理n个偶数,所以时间复杂度是
空间复杂度:需要额外大小为的set来储存,所以空间复杂度为