算法筆試模拟題精解之“調整數組”

線上程式設計介紹

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

https://developer.aliyun.com/coding

本文為大家介紹其中的 第89題：調整數組 的題目解析，具體如下：

題目描述

等級：中等

知識點：尺取法

檢視題目：調整數組

A同學有一個長度為n的數組，對于這個數組，他能夠進行k次如下操作：任選數組中的某個元素将其數值加一（一個元素可以被加多次）。

他想在操作不超過k次的情況下，使得數組中某一進制素的出現次數盡可能的多，并同時使這個元素盡可能的小。

請你找出出現次數最多的元素的出現次數以及此時這個元素的最小值。

輸入:

輸入數組長度n(1 <= n <= 10^5)，最多能操作次數k(1 <= k <= 10^5)，和一個包含n個數的數組，數組中第i個元素的值為ai(0 <= ai <= 10^4)。

輸出:

輸出操作後出現次數最多的元素的出現次數以及此時這個元素的最小值。

解題方法：模拟法

變量概述

• int n : 有n個數
• int k : 最多操作k次
• int[] a : 存儲n個數的數組
• 隻能對a[i]進行一種操作 : +1

首先了解題意：經過k次操作後能出現次數最多的元素, 以及這個元素的最小值；

示例說明：

• 1 2 2 3 3 4

兩個3要變成4就得操作2次

兩個2要變成4就得操作4次

• 因為 ai 的大小被限定在[0, 10^4], 是以可以使用一個數組arr, 來統計每個數字出現的次數。
• 周遊數組arr, 對于任意不等于0的數arr[i], 逆向周遊前面所有

  *不為0的***arr[j]**

  , 并對每個不為0的arr[j],

  **k-=arr[j] * (i-j)**

  , 直到k不夠減或沒前面沒數字了。
• 如果是k不夠減, 則得在判斷k能夠再減去多少個arr[j], 因為之前的公式是計算減去所有的arr[j]的
• 之是以要不為0的, 是因為壓根沒有這個數, 無法對其進行+操作

解題步驟

1、定義變量

• int[] arr : 用來存儲每個數字出現的次數, 容量為10001
• int max : 用來存儲最大次數, 初始化為1
• int maxValue : 用來存儲最大次數所對應的最小值, 随着最大次數的更新而更新, 初始化為a[0]
• int k1 : 用來備份k值, 避免k值計算後不見了
• int temp : 用來統計目前最大數字出現的次數, 初始化為arr[i]

2、周遊數組arr, 找出出現最多的次數以及對應的最小值.

• 對于每個arr[j] 如果arr[j]為0, 則直接跳過. 不是不加，而是沒法加
• 如果arr[j] * (i-j) <= k, 證明目前的操作次數能夠将j全部變成i, 則使用temp加上所有的j
• 如果arr[j] * (i-j) > k, 則證明目前次數k無法将全部j變成i，開始嘗試将部分j轉成i
  • 使用k/(i-j)計算還能夠将多少個j轉成i，然後進行轉換
  • 判斷temp和最大值是否大于最大次數max, 如果大于, 則更新max和maxValue
• 注意: 當arr[j]順利周遊到arr[0]時退出循環, 因為我們的比較最大值操作是在循環内進行的, 是以此時, 可能無法對max進行更新, 是以需要在手動判斷一次temp和max的大小

3、傳回數組

時間複雜度: O（n^2）

空間複雜度: O（n）

看完之後是不是有了想法了呢，快來練練手吧>>