题解 | #牛牛爱奇数#

题意整理

给定n个数，将这n个数中所有的偶数变为奇数。
为了将偶数变为奇数，可以执行除2操作。
求最少需要操作多少次，可以将所有的数变为奇数。

方法一（Set）

1.解题思路

遍历所有的数。
如果是偶数，则执行除2操作，直到最后的结果不再是偶数，并且记录下所有处理过的偶数。访问其它偶数时，如果已经在set中，则不需要再处理。
每执行一次除2操作，计数加一。最后的计数即是最少操作的次数

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回一个数，代表让这些数都变成奇数的最少的操作次数
     * @param n int整型 代表一共有多少数
     * @param a int整型一维数组 代表n个数字的值
     * @return int整型
     */
    public int oddNumber (int n, int[] a) {
        //用于记录处理过的偶数
        Set<Integer> set=new HashSet<>();
        int cnt=0;
        for(int i=0;i<n;i++){
            //如果某个偶数没处理，则加入到set，一直执行除2操作，直到结果不再是偶数
            while(a[i]%2==0&&!set.contains(a[i])){
                set.add(a[i]);
                a[i]/=2;
                //计数加一
                cnt++;
            }
        }
        return cnt;
    }
}

3.复杂度分析

时间复杂度：最坏情况下，所有数都是偶数，需要处理n个偶数，假设n个偶数在除2过程中没有重复的中间值，并且需要执行k次除2操作变为偶数，则时间复杂度为 $O(n*k)$ 。
空间复杂度：需要额外大小为n*k的set，所以空间复杂度为 $O(n*k)$ 。

方法二（TreeSet）

1.解题思路

遍历所有的数，将偶数加入到TreeSet。
每次取出当前最大偶数，如果除2之后还是偶数，则将除2之后的结果加入到set，移除掉当前最大偶数。每次操作将计数加1.
最终的计数即是最少操作的次数

动图展示：
图片说明

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回一个数，代表让这些数都变成奇数的最少的操作次数
     * @param n int整型 代表一共有多少数
     * @param a int整型一维数组 代表n个数字的值
     * @return int整型
     */
    public int oddNumber (int n, int[] a) {
        //用于记录剩下的偶数
        TreeSet<Integer> set=new TreeSet<>();
        for(int i=0;i<n;i++){
            //添加所有偶数
            if(a[i]%2==0){
                set.add(a[i]);
            }
        }
        int cnt=0;
        while(!set.isEmpty()){
            //取出最大偶数
            int max=set.last();
            //如果除2还是偶数，则继续加入到set
            if((max/2)%2==0){
                set.add(max/2);
            }
            //移除掉当前最大的偶数
            set.pollLast();
            //计数加一
            cnt++;
        }
        return cnt;
    }
}

3.复杂度分析

时间复杂度：最坏情况下，所有数都是偶数，需要处理n个偶数，每添加一个元素到TreeSet，需要 $O(logn)$ 的时间复杂度，所以添加的时间复杂度为 $O(n*logn)$ ，假设从set移除的偶数不会产生重复的中间值，并且每个偶数移除次数为k，则移除的时间复杂度为 $O(n*k*logn)$ ，所以最终的时间复杂度为 $O(n*k*logn)$ 。
空间复杂度：需要额外大小为n的set，所以空间复杂度为 $O(n)$ 。