描述

在牛牛面前放着nn个数，这些数字既有奇数也有偶数，只不过牛牛对奇数情有独钟，他特别想让这些数都变成奇数。
现在牛牛获得了一种能力，他可以执行一种操作：每次选中一个偶数，然后把这些数中与该数相等的数都除以2，例如现在有一个数组为[2,2,3][2,2,3]，那么牛牛可以执行一次操作，使得这个数组变为[1,1,3][1,1,3]。
牛牛现在想知道，对于任意的nn个数，他最少需要操作多少次，使得这些数都变成奇数？

示例1

输入：
3,[2,2,3]

返回值：
1

说明：
只需做一次操作，会将其中的偶数2都变成1，满足了所有的数都是奇数的要求。

示例2

输入：
3,[1,3,7]

返回值：
0

说明：
不需要做任何操作，因为所有的数原本就是奇数。

思路

这道题其实就是 找到所有的偶数，然后选中一个偶数除以 2， 并且相同的偶数都会执行除以2的操作。然后统计操作的次数。
其实咱们也不用非得所有数都除以2，每个数除以 2 之后给记录下来，以后碰到这个 数之后就跳过不用处理即可。

如上图：

• 开始遍历数组，遇到第一个偶数先放入一个去重集合中，然后对该偶数除以2，如果还是偶数的话，在放入集合中在除以2，直到变为奇数为止。
• 继续遍历数组，如果遇到偶数并且在集合中就跳过，否则继续执行上面操作。
• 每次除以2时就将次数 + 1.

AC 代码

public int oddNumber (int n, int[] a) {
        // write code here
        if (a == null || a.length < 1) {
            return 0;
        }
        // 去重集合
        Set<Integer> set = new HashSet<>();
        // 总的次数
        int count = 0;
        // 遍历数组
        for (int i = 0; i < a.length; i ++) {
            // 如果时 偶数 并且不再集合中
            while ((a[i] & 1) == 0 && !set.contains(a[i])) {
                // 先加入去重集合
                set.add(a[i]);
                // 除以2
                a[i] /= 2;
                // 次数 ++
                count ++;
            }
        }
        return count;
    }

• 时间复杂度：O(N)， N 为数组长度，因为每个元素都要遍历一次。
• 空间复杂度：O(N)， 最坏的情况时每个元素都存储在集合中。

最后

大家有兴趣可以来我的牛客博客中看看其他内容，兴许对你有所帮助。