資訊專欄INFORMATION COLUMN
摘要：所以說，要使所有數(shù)相等，可以等價轉(zhuǎn)換為所有數(shù)都減到和一樣大。于是思路變成了找到累加每個數(shù)與的差值。于是只需要一次遍歷，一邊求和，一邊找到，最后返回即可。
LC453
這是準備coursera OA遇到的一個easy卻有趣的題，一開始我想的是先排序，然后不停找出最小值，前n-1個數(shù)加1...總之就是時間復(fù)雜度太高無法AC，這時候我覺得無法AC的easy題肯定是要用一些數(shù)學上的巧辦法了，google之，于是整理如下：
每做一次move，相當于除了最后一位數(shù)之外所有數(shù)+1，換個角度想其實是最后一位數(shù)-1： [1,2,3] ---> [2, 2, 3] = [1, 2, 2]效果是一樣的。所以說，要使所有數(shù)相等，可以等價轉(zhuǎn)換為所有數(shù)都減到和min一樣大。于是思路變成了“找到min -> 累加每個數(shù)與min的差值”。繼續(xù)優(yōu)化，因為找到Min至少需要一次遍歷，累加又是一次遍歷，有沒有辦法同一次遍歷搞定所有事情呢？很簡單，對于數(shù)組[a1,a2,a3,...,an] 累加 (a1 - min) + (a2 - min) + (a3 - min) + ... + (an - min) = ∑a - n x min（sf怎么打星號就變成了斜體...）。 于是只需要一次遍歷，一邊求和，一邊找到Min，最后返回sum - nums.length x min即可。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/68358.html
摘要：通過使用其構(gòu)造函數(shù)，可以將一個值的類型轉(zhuǎn)換為另一種類型。如果使用兩次，可用于將該值轉(zhuǎn)換為相應(yīng)的布爾值。 編譯自：[1] + [2] – [3] === 9!? Looking into assembly code of coercion.全文從兩個題目來介紹類型轉(zhuǎn)換、寬松相等以及原始值的概念: [1] + [2] – [3] === 9 如果讓 a == true && a == fa...
摘要：前言月份開始出沒社區(qū)，現(xiàn)在差不多月了，按照工作的說法，就是差不多過了三個月的試用期，準備轉(zhuǎn)正了一般來說，差不多到了轉(zhuǎn)正的時候，會進行總結(jié)或者分享會議那么今天我就把看過的一些學習資源主要是博客，博文推薦分享給大家。 1.前言 6月份開始出沒社區(qū)，現(xiàn)在差不多9月了，按照工作的說法，就是差不多過了三個月的試用期，準備轉(zhuǎn)正了！一般來說，差不多到了轉(zhuǎn)正的時候，會進行總結(jié)或者分享會議！那么今天我就...
摘要：現(xiàn)如今編程這個行當，也約定俗成出了一個入行儀式，就是選你將要使用的編程語言，寫段代碼輸出，這片文章講的就是這么個事寫個函數(shù)輸出，請真的不要覺得很簡單。但每行兩個字符的限制，是把函數(shù)創(chuàng)建的生門堵死了。 自古，三百六十行，每一行入行的時候都有個儀式。現(xiàn)如今編程這個行當，也約定俗成出了一個入行儀式，就是選你將要使用的編程語言，寫段代碼輸出hello world!，這片文章講的就是這么個事——...
閱讀 1887·2021-11-15 11:46
閱讀 1077·2021-10-26 09:49
閱讀 1820·2021-10-14 09:42
閱讀 3374·2021-09-26 09:55
閱讀 827·2019-08-30 13:58
閱讀 1024·2019-08-29 16:40
閱讀 3462·2019-08-26 10:27
閱讀 601·2019-08-23 18:18
