题解 | #牛牛爱奇数#

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;
    }
};

时间复杂度： $O(nlogn)$ 对整个序列进行遍历，对于偶数不断进行除以2的操作，所以时间复杂度是 $O(nlogn)$
空间复杂度： $O(n)$ 需要额外的空间对相同偶数需要次数的记录
三.算法(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个偶数，所以时间复杂度是 $O(nlogn)$
空间复杂度：需要额外大小为 $nlogn$ 的set来储存，所以空间复杂度为 $O(nlogn)$ 。