作者stayhungry (跳跳跳跳虎)
看板C_and_CPP
標題[問題] LeetCode 136.Single Number
時間Sat Mar 16 15:02:12 2019
開發平台(Platform): (Ex: Win10, Linux, ...)
Win8.1
編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
GCC
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
問題(Question)：
各位前輩大家好
主要問題是在Code Blocks執行時能回傳正確的結果，但在leetcode 會顯示error，想請教error 的原因及如何修改程式碼
題目要求是輸入一個整數陣列，回傳只在陣列中出現一次的數字，答案唯一。
我的想法是先用qsort()將陣列中的數字排序，排序完
如果第一個數字 不等於 第二個數字
=>回傳第一個數字
如果最後一個數字 不等於 倒數第二個數字
=>回傳最後一個數字
如果第 i 個數字不等於第 i - 1個數字且不等於第 i + 1個數字( i 為第二個數字～倒數第二個數字)
=>回傳第 i 個數字
餵入的資料(Input)：
{2, 3, 4, 2, 5, 4, 3}
預期的正確結果(Expected Output)：
在Code Blocks 執行完回傳5，為正確預期結果
錯誤結果(Wrong Output)：
在leetcode submit 之後，顯示 runtime error :heap-buffer-overflow
程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔)
https://pastebin.com/rDDm8Nr9
補充說明(Supplement)：
-----
Sent from JPTT on my Asus ASUS_Z01KDA.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.121.55.226
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1552719735.A.DFB.html
※ 編輯: stayhungry (122.121.55.226), 03/16/2019 15:06:43
※ 編輯: stayhungry (122.121.55.226), 03/16/2019 15:08:59
推 idiont: Note: 03/16 15:26
→ idiont: Your algorithm should have a linear runtime complexity 03/16 15:26
→ idiont: . Could you implement it without using extra memory? 03/16 15:26
→ aa0917954358: array的長度如果是0或1就會爆了吧？ 03/16 15:27
→ stayhungry: 感謝大大，只注意到題目寫陣列為non-empty，忘了考慮 03/16 15:45
→ stayhungry: 到只有一個元素的情況，在leetcode 加上條件 03/16 15:45
→ stayhungry: if(numsSize == 1) return nums[0]可以順利執行 03/16 15:45
→ stayhungry: qsort 的runtime也有可能是error的原因嗎？ 03/16 15:52
→ stayhungry: 查cplusplus.com的qsort complexity :Unspecified,but 03/16 15:52
→ stayhungry: quicksorts are generally linearithmic in num,on a 03/16 15:52
→ stayhungry: verage,calling compar approximately num*log2(num) 03/16 15:52