算法筆試模拟題精解之“全奇數組”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

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)

看完之後是不是有了想法了呢，題目直達連結：