【LeetCode】977. Squares of a Sorted Array

閱讀時間約 2 分鐘

今天的題目示例如下:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

簡單來說,要的輸出結果是把陣列內每個數字取平方後,對陣列做排序。

使用內建的排序方法

如此一來是完成了沒錯,但...好像什麼都沒練到。於是用了時間複雜度O(nlogn)的合併排序法練習,替代了排序的部分。

採用mergeSort

合併排序法採遞迴的方式,將原本的陣列從中間分成左右兩半,比較取值後覆寫回原本的陣列。

建立兩個新的陣列(左子陣列、右子陣列)

比較左右子陣列,依序放入原陣列覆寫

提交出的結果效能時間跟空間使用都很穩定,穩定的輸給內建的排序。

另外,取平方的作法原則上可以使用Math.pow() 得到次方結果,型態是double。印象中以前課堂上特別被點出,如果只是取平方的需求,讓數字跟自己相乘就好,次方函數的運作採用類似泰勒展開的近似法趨近,效能上還是有差別。

avatar-img
13會員
64內容數
遇到的坑、解過的題、新知識的探索、舊時代的遺毒!? 工作後我發現,文件更新往往跟不上新需求的更迭,犯錯的歷史總是不斷重演。因此,我改變了方式,蒐集從程式上、系統上的每一次異常處理過程,好讓再次遇到相同的問題時能快速應變。此專題就是我的錯題本,期待日後不管在工作上或交流上遇到難題,都能輕鬆地應答:有什麼難的,我都踩過。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
Err500 的其他內容
Leetcode上正好有14天的讀書計畫,今天三題都是二分搜索,順手三題都寫一寫,想法上很固定。
前幾天看別人直播刷題,心血來潮打開很久沒動的leetcode試試,挑了一題當初面試沒寫出來的題目。嗯...我那時才剛碰資料結構,知道要用stack寫卻沒實作過任何東西,現在有工作經驗後再來寫,看看會不會有不一樣的想法。
即將到職滿一周年,平時每幾個月就會記錄一下期間內做了什麼、學了什麼,算是給自己的總回顧...
輸入畫面 為什麼要做驗證? 因為作為設計者,永遠不該預設使用者會乖乖照設計者的意思輸入。
前言 目前手邊工作上,與其說是開發新功能,大多時候比較常是優化原有的功能,順便修正以前留下來的bug,因此解讀前人的程式碼、留不留註解、如何讓程式寫的更"乾淨"一點等常見的問題一件一件浮上檯面。
剛結束公司的內部訓練,對我自己來說,收穫最多的部分並不是來自課程內容,反而是與一同參加課程,來自各部門、不同學經歷的同事們的交流閒談,看看從不同背景、不同角度看待同一件事情,會出現哪些自己從來沒發現過的盲點。
Leetcode上正好有14天的讀書計畫,今天三題都是二分搜索,順手三題都寫一寫,想法上很固定。
前幾天看別人直播刷題,心血來潮打開很久沒動的leetcode試試,挑了一題當初面試沒寫出來的題目。嗯...我那時才剛碰資料結構,知道要用stack寫卻沒實作過任何東西,現在有工作經驗後再來寫,看看會不會有不一樣的想法。
即將到職滿一周年,平時每幾個月就會記錄一下期間內做了什麼、學了什麼,算是給自己的總回顧...
輸入畫面 為什麼要做驗證? 因為作為設計者,永遠不該預設使用者會乖乖照設計者的意思輸入。
前言 目前手邊工作上,與其說是開發新功能,大多時候比較常是優化原有的功能,順便修正以前留下來的bug,因此解讀前人的程式碼、留不留註解、如何讓程式寫的更"乾淨"一點等常見的問題一件一件浮上檯面。
剛結束公司的內部訓練,對我自己來說,收穫最多的部分並不是來自課程內容,反而是與一同參加課程,來自各部門、不同學經歷的同事們的交流閒談,看看從不同背景、不同角度看待同一件事情,會出現哪些自己從來沒發現過的盲點。
你可能也想看
Google News 追蹤
Thumbnail
徵的就是你 🫵 超ㄅㄧㄤˋ 獎品搭配超瞎趴的四大主題,等你踹共啦!還有機會獲得經典的「偉士牌樂高」喔!馬上來參加本次的活動吧!
Thumbnail
隨著理財資訊的普及,越來越多台灣人不再將資產侷限於台股,而是將視野拓展到國際市場。特別是美國市場,其豐富的理財選擇,讓不少人開始思考將資金配置於海外市場的可能性。 然而,要參與美國市場並不只是盲目跟隨標的這麼簡單,而是需要策略和方式,尤其對新手而言,除了選股以外還會遇到語言、開戶流程、Ap
Thumbnail
題目敘述 Sort Array by Increasing Frequency Leetcode #1636 給定一個輸入陣列,請依照出現頻率的多寡從低頻到高頻排列陣列元素。 如果有兩個元素的出現頻率相同,依照元素大小從大到小排列。 測試範例 Example 1: Input: nums
Thumbnail
給定一個輸入非負整樹陣列nums,請找出k值,使得陣列中恰好有k個元素大於等於 k。如果無解,回傳-1。尋找k值的方法包括排序法和二分搜尋法,時間複雜度都為O(n log n),空間複雜度為O(1)。關鍵知識點是當解空間具有遞增或遞減的性質時,可以用二分搜尋法加快搜尋效率。
Thumbnail
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值,那如果我們在迭代中對陣列操作會發生什麼事? 題目來源:https://x.com/_jayphelps/status/1774640511158022335?s=20
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目敘述 題目會給定我們一個輸入陣列nums,要求我們掃描美個陣列元素nums[i],計算除了nums[i]以外的陣列元素連乘積。 題目的原文敘述 測試範例 Example 1: Input: nums = [1,2,3,4] Output: [24,12,8,6] nums[0] 以
Thumbnail
題目敘述 題目會給定我們兩個整數陣列作為輸入nums1, nums2,要求我們找出兩個陣列的差異值。 找出在nums1但是不在nums2的元素,以陣列的形式放在answer[0]輸出。 找出在nums2但是不在nums1的元素,以陣列的形式放在answer[1]輸出。 題目的原文敘述
Thumbnail
題目敘述 題目會給定我們一個整數陣列nums,要求我們把裡面的0做元素交換,把0都搬到陣列的右邊。題目要求必須in-place在原本的陣列裡面做操作,不可以額外建立新的陣列。 題目的原文敘述 測試範例 Example 1: Input: nums = [0,1,0,3,12] Outpu
Thumbnail
題目敘述 題目給定我們一個輸入陣列nums 要求我們以正、負交叉排列的方式重組陣列,並且必須保持原本的相對順序。 並且以陣列的形式輸出返回答案。 例[5, 1, -2, -3] 重排後為 [5, -2, 1, -3] 題目的原文敘述 測試範例 Example 1: Input:
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,和一個指定的k值。 請問,在輸入陣列nums中,有幾個子陣列的元素總合恰好為k ? 例如: nums = [1,2,3], k = 3 則有兩個子陣列的元素總合為3,分別是[1,2] 和 [3] 如果是第一次聽到或接觸前綴和prefix的同學
Thumbnail
徵的就是你 🫵 超ㄅㄧㄤˋ 獎品搭配超瞎趴的四大主題,等你踹共啦!還有機會獲得經典的「偉士牌樂高」喔!馬上來參加本次的活動吧!
Thumbnail
隨著理財資訊的普及,越來越多台灣人不再將資產侷限於台股,而是將視野拓展到國際市場。特別是美國市場,其豐富的理財選擇,讓不少人開始思考將資金配置於海外市場的可能性。 然而,要參與美國市場並不只是盲目跟隨標的這麼簡單,而是需要策略和方式,尤其對新手而言,除了選股以外還會遇到語言、開戶流程、Ap
Thumbnail
題目敘述 Sort Array by Increasing Frequency Leetcode #1636 給定一個輸入陣列,請依照出現頻率的多寡從低頻到高頻排列陣列元素。 如果有兩個元素的出現頻率相同,依照元素大小從大到小排列。 測試範例 Example 1: Input: nums
Thumbnail
給定一個輸入非負整樹陣列nums,請找出k值,使得陣列中恰好有k個元素大於等於 k。如果無解,回傳-1。尋找k值的方法包括排序法和二分搜尋法,時間複雜度都為O(n log n),空間複雜度為O(1)。關鍵知識點是當解空間具有遞增或遞減的性質時,可以用二分搜尋法加快搜尋效率。
Thumbnail
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值,那如果我們在迭代中對陣列操作會發生什麼事? 題目來源:https://x.com/_jayphelps/status/1774640511158022335?s=20
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目敘述 題目會給定我們一個輸入陣列nums,要求我們掃描美個陣列元素nums[i],計算除了nums[i]以外的陣列元素連乘積。 題目的原文敘述 測試範例 Example 1: Input: nums = [1,2,3,4] Output: [24,12,8,6] nums[0] 以
Thumbnail
題目敘述 題目會給定我們兩個整數陣列作為輸入nums1, nums2,要求我們找出兩個陣列的差異值。 找出在nums1但是不在nums2的元素,以陣列的形式放在answer[0]輸出。 找出在nums2但是不在nums1的元素,以陣列的形式放在answer[1]輸出。 題目的原文敘述
Thumbnail
題目敘述 題目會給定我們一個整數陣列nums,要求我們把裡面的0做元素交換,把0都搬到陣列的右邊。題目要求必須in-place在原本的陣列裡面做操作,不可以額外建立新的陣列。 題目的原文敘述 測試範例 Example 1: Input: nums = [0,1,0,3,12] Outpu
Thumbnail
題目敘述 題目給定我們一個輸入陣列nums 要求我們以正、負交叉排列的方式重組陣列,並且必須保持原本的相對順序。 並且以陣列的形式輸出返回答案。 例[5, 1, -2, -3] 重排後為 [5, -2, 1, -3] 題目的原文敘述 測試範例 Example 1: Input:
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,和一個指定的k值。 請問,在輸入陣列nums中,有幾個子陣列的元素總合恰好為k ? 例如: nums = [1,2,3], k = 3 則有兩個子陣列的元素總合為3,分別是[1,2] 和 [3] 如果是第一次聽到或接觸前綴和prefix的同學