第一次用簡書辞色,注冊登錄快捷,界面像oneNote浮定。
數(shù)組理論基礎
第一時間想到的就是連續(xù)的一段空間相满,可以隨機訪問,添加刪除的時間復雜度是o(n),訪問桦卒,修改時間復雜度o(1) 立美,看了代碼隨想錄后覺得還能再補充一寫理論,知道但是不會立馬說出口的方灾。
數(shù)組:連續(xù)空間上 相同數(shù)據(jù)類型 的 集合
java中的二維數(shù)組不是連續(xù)的建蹄,類似拉鏈法的形狀
704.二分查找
雖然做過這道題,但是完全不會想到要用二分查找裕偿,思維有很大的開闊空間洞慎。
需要學習的:二分法的兩種寫法。[ ],[ )
關(guān)于 是否用<= ,<嘿棘。邊界處理拢蛋。訣竅在于帶入數(shù)值看是否是合法區(qū)間。
1.左閉右閉蔫巩。
[1,1]是合法區(qū)間谆棱,所以在while時,left=right是可以取到的圆仔,所以可以寫成while(left<=right)垃瞧。
target<middle時,right應該換成middle坪郭,但這里需要考慮是middle還是middle-1个从。顯然閉區(qū)間middle是可以取到且已知middle>target了,所以新的right不應該包含middle這個值歪沃,即right = middle - 1嗦锐;
target>middle時,left應該換成middle+1沪曙。?
2.左閉右開
[1,1)不合法奕污,left=right不能取到,while(left<right)
target<middle時液走,right應該換成middle碳默,但這里需要考慮是middle還是middle-1。顯然開區(qū)間middle是不可以取到的缘眶,所以新的right可以包含middle這個值嘱根,即right = middle ;
target>middle時巷懈,同理閉區(qū)間可以取到该抒,left應該換成middle+1
關(guān)于取中間值,自己實現(xiàn)的時候用的是(L+R)/ 2 顶燕,且自己實現(xiàn)的時候不能通過凑保,評論區(qū)有人指出這樣會造成整型溢出,減法則不會割岛∮涫剩可以接受的減法是 L+ (R-L)/2.
27.移除元素
只能想到暴力解法。
nums.erase是o(n)的算法癣漆。這里雙指針也是o(n)
需要學習的:雙指針维咸。 數(shù)組的元素不能被刪除,只能覆蓋惠爽。因為數(shù)組所占的區(qū)域已經(jīng)分給它了癌蓖,而且是連續(xù)的,不能刪除單個元素婚肆。
快慢指針原地修改值租副。原理是慢指針記錄數(shù)組的長度,快指針遍歷數(shù)組記錄需要更新的數(shù)值较性,當數(shù)值等于val(需要移除的元素)時用僧,則不往新的數(shù)組里加入结胀。