在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的第62题：全奇数组 的题目解析，具体如下：

题目描述

题目等级：中等
知识点：堆、贪心、哈希
查看题目：全奇数组 codancer现在有n个正整数a[1],a[2]…a[n]，Tom告诉codancer他可以进行下列操作，选择某个偶数x，把这n个数中全部等于x的数字除2，Tom想知道把这n个数字全部变成奇数最少需要几次这样的操作？

输入一个正整数n(1<=n<=100000)，代表有n个正整数，接下来输入这n个正整数。

输出codancer把这n个数字全部变成奇数的最少次数。

示例1
输入：
6
[40,6,40,3,20,1]
输出：
4
注意
1.x=40,数组变为
[20,6,20,3,20,1]
2.x=20，数组变为
[10,6,10,3,10,1]
3.x=10,数组变为
[5,6,5,3,5,1]
4.x=6，数组变为
[5,3,5,3,5,1]
因此最少需要4次

解题思路

从题意及示例可以知道，应该从大到小进行操作。当除2后，需要快速查找是否有相等的其他数，这个需求可以使用HashSet代替。

因此，先将n个中的偶数入HashSet，再对HashSet中元素从大到小排序，依次遍历；

每个元素除2后从HashSet查找，存在则移除，计数+1，直到该数变成奇数。

最坏情况下，除2过程没有重复数字
时间复杂度：O(n+n*n/2)
空间复杂度：O(n)

看完之后是不是有了想法了呢，题目直达链接：查看题目：全奇数组