iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 18
0
自我挑戰組

[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ系列 第 18

[LeetCode with JavaScript] Day 18: Missing Number

觀前提醒:

  1. 我預設大家已經先思考並分析過題目,沒啥想法才開始 google 找解題靈感。若無,建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法
  2. 承上,既然已經有思考過了,那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了,那我可能解題想法 & 心得的部分就不會寫太多,免得干擾你的思考。
  3. 所有解法都是已經取得系統的 Accepted,但或許不是最優解法,請多包涵。
  4. 若對於解法不太懂,可以嘗試用 Chrome 的 debugger 來試跑看看 (教學文)
  5. 最後,歡迎在下面留言指教~教學相長才會進步歐~/images/emoticon/emoticon41.gif

題目

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

解題想法

因為我觀察過題目後,發現到測資都是給定一個從0開始,公差為1的等差數列。
所以,我所採用的是數學解:等差數列和 - 整包數列和 = 消失的數字。

CODE

/**
 * @param {number[]} nums
 * @return {number}
 */

// 等差數列和 - 整包數列和 = 消失的數字。
 var missingNumber = function (nums) {
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
  }

  // arithmetic progression (s1 + sn) * n / 2
  return (1 + nums.length) / 2 * nums.length - sum;
};

心得

其實這題,也是可以用.indexOf() 來解,但這樣就沒辦法練習到數學方面的解法,故今天僅撰寫數學解的部分。
各位兄弟姊妹有空的話,也可以嘗試用 .indexOf()來寫寫看,這不會很困難歐~
/images/emoticon/emoticon12.gif


謝謝大家的收看,LeetCode 小學堂我們下次見~/images/emoticon/emoticon29.gif


上一篇
[LeetCode with JavaScript] Day 17: Fibonacci_Number
下一篇
[LeetCode with JavaScript] Day 19: Number of 1 Bits
系列文
[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言