您好,登錄后才能下訂單哦!
這篇文章主要介紹“Java數(shù)組高頻考點(diǎn)實(shí)例分析”的相關(guān)知識,小編通過實(shí)際案例向大家展示操作過程,操作方法簡單快捷,實(shí)用性強(qiáng),希望這篇“Java數(shù)組高頻考點(diǎn)實(shí)例分析”文章能幫助大家解決問題。
數(shù)組是存放在連續(xù)內(nèi)存空間上的相同類型數(shù)據(jù)的集合,可以通過下標(biāo)索引的方式獲取到下標(biāo)下對應(yīng)的數(shù)據(jù)。
舉個栗子(字符數(shù)組)~
可以看到:
1、數(shù)組的下標(biāo)從0開始
2、數(shù)組在內(nèi)存中的地址是連續(xù)的
所以在刪除元素時,只能用覆蓋的方式進(jìn)行。
例如,要刪除下標(biāo)為2的元素~ 就需要將從2之后的元素依次移到前一個,覆蓋掉要刪除的元素。
所以刪除元素并不是將該元素的空間釋放了,而是將后面的元素移到前面,覆蓋掉要刪除的元素,然后將數(shù)組的長度減去1,就能得到一個看似新的數(shù)組。
在java中,二維數(shù)組的存儲方式如下:
力扣題目鏈接: 二分查找
這道題目的前提是有序數(shù)組,因?yàn)橐坏┯兄貜?fù)元素,使用二分查找法返回的元素下標(biāo)可能不是唯一的,這些都是使用二分法的前提條件。
二分查找思想是:
數(shù)組有序的前提下(假設(shè)升序),如果數(shù)組中間的值大于要查找的值,那么要查找的元素就不可能在后半部分,因?yàn)楹蟀氩糠值闹刀即笥谥虚g的值,所以通過第一次比較,就可以將范圍縮小一半,后面同理,即時間復(fù)雜度降到了O(logN),效率大大提高,當(dāng)題目中要求查找元素的時間復(fù)雜度為O(logN)時,首先想一想是否能用二分呢?
class Solution { public int search(int[] nums, int target) { // 避免當(dāng) target 小于nums[0] nums[nums.length - 1]時多次循環(huán)運(yùn)算 if (target < nums[0] || target > nums[nums.length - 1]) { return -1; } int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + ((right - left) >> 1); if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right = mid - 1; } return -1; } }
有的同學(xué)可能說了,多余的元素,刪掉不就得了?但是要知道數(shù)組的元素在內(nèi)存地址中是連續(xù)的,不能單獨(dú)刪除數(shù)組中的某個元素,只能覆蓋。
例如:給你一個數(shù)組和一個val值,要求刪除數(shù)組中等于val值的元素,怎么做呢?
思路1:暴力法
我們可以使用兩個for循環(huán),當(dāng)遍歷到等于val值的元素時,就將后面的元素整體往前移一個覆蓋掉要刪除的元素,但是這種做法顯然時間復(fù)雜度太高。
class Solution { public int removeElement(int[] nums, int val) { int size = nums.length; for (int i = 0; i < size;i++ ) { if (nums[i] == val) { // 發(fā)現(xiàn)需要移除的元素,就將數(shù)組后面集體向前移動一位 for (int j = i + 1; j < size; j++) { nums[j - 1] = nums[j]; } i--; // 因?yàn)橄聵?biāo)i以后的數(shù)值都向前移動了一位,所以i也向前移動一位 size--; } } return size; } }
思路2:雙指針法
分別設(shè)設(shè)一個快慢指針,slow fast ,兩者一起走,當(dāng)慢指針遇到要刪除的元素時停下,等待著被刪除(覆蓋);當(dāng)快指針走到要被留下的元素時,將快指針的元素賦值給慢指針,然后兩指針同時向后走,直到快指針遍歷完整個數(shù)組。
可以這么理解:定義數(shù)組的新長度newLength ,從0開始,定義一個快指針遍歷數(shù)組 fast,當(dāng)fast走到要被留下的元素時,說明該元素應(yīng)該被添加到新數(shù)組中(即被添加到newLength 下標(biāo),這里相當(dāng)于 newLength 之前的部分?jǐn)?shù)組看做要返回的新數(shù)組,相當(dāng)于往這個新數(shù)組里插入元素)。
class Solution { public int removeElement(int[] nums, int val) { int fast = 0;// 定義一個快指針遍歷數(shù)組 int newLength = 0;// 定義新的數(shù)組長度 while(fast < nums.length){ if(nums[fast] != val){ nums[newLength++] = nums[fast]; } fast++; } return newLength; } }
推薦力扣題目
1.刪除排序數(shù)組中的重復(fù)項(xiàng)
2.移動零
3.比較含退格的字符串
4.有序數(shù)組的平方
其他常見數(shù)組的考點(diǎn)很多都是以這兩點(diǎn)為基礎(chǔ),無非就是對數(shù)組增刪改查,將數(shù)組的查找和刪除掌握了,就可以開始刷題啦。
關(guān)于“Java數(shù)組高頻考點(diǎn)實(shí)例分析”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識,可以關(guān)注億速云行業(yè)資訊頻道,小編每天都會為大家更新不同的知識點(diǎn)。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。