Java 數(shù)組高頻考點(diǎn)分析講解
1、數(shù)組理論基礎(chǔ)
數(shù)組是存放在連續(xù)內(nèi)存空間上的相同類型數(shù)據(jù)的集合,可以通過下標(biāo)索引的方式獲取到下標(biāo)下對(duì)應(yīng)的數(shù)據(jù)。
舉個(gè)栗子(字符數(shù)組)~
可以看到:
1、數(shù)組的下標(biāo)從0開始
2、數(shù)組在內(nèi)存中的地址是連續(xù)的
所以在刪除元素時(shí),只能用覆蓋的方式進(jìn)行。
例如,要?jiǎng)h除下標(biāo)為2的元素~ 就需要將從2之后的元素依次移到前一個(gè),覆蓋掉要?jiǎng)h除的元素。
所以刪除元素并不是將該元素的空間釋放了,而是將后面的元素移到前面,覆蓋掉要?jiǎng)h除的元素,然后將數(shù)組的長(zhǎng)度減去1,就能得到一個(gè)看似新的數(shù)組。
在java中,二維數(shù)組的存儲(chǔ)方式如下:
2、常見考點(diǎn)
1.二分查找
力扣題目鏈接: 二分查找
這道題目的前提是有序數(shù)組,因?yàn)橐坏┯兄貜?fù)元素,使用二分查找法返回的元素下標(biāo)可能不是唯一的,這些都是使用二分法的前提條件。
二分查找思想是:
數(shù)組有序的前提下(假設(shè)升序),如果數(shù)組中間的值大于要查找的值,那么要查找的元素就不可能在后半部分,因?yàn)楹蟀氩糠值闹刀即笥谥虚g的值,所以通過第一次比較,就可以將范圍縮小一半,后面同理,即時(shí)間復(fù)雜度降到了O(logN),效率大大提高,當(dāng)題目中要求查找元素的時(shí)間復(fù)雜度為O(logN)時(shí),首先想一想是否能用二分呢?
class Solution { public int search(int[] nums, int target) { // 避免當(dāng) target 小于nums[0] nums[nums.length - 1]時(shí)多次循環(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; } }
2.移除元素
有的同學(xué)可能說了,多余的元素,刪掉不就得了?但是要知道數(shù)組的元素在內(nèi)存地址中是連續(xù)的,不能單獨(dú)刪除數(shù)組中的某個(gè)元素,只能覆蓋。
例如:給你一個(gè)數(shù)組和一個(gè)val值,要求刪除數(shù)組中等于val值的元素,怎么做呢?
思路1:暴力法
我們可以使用兩個(gè)for循環(huán),當(dāng)遍歷到等于val值的元素時(shí),就將后面的元素整體往前移一個(gè)覆蓋掉要?jiǎng)h除的元素,但是這種做法顯然時(shí)間復(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ù)組后面集體向前移動(dòng)一位 for (int j = i + 1; j < size; j++) { nums[j - 1] = nums[j]; } i--; // 因?yàn)橄聵?biāo)i以后的數(shù)值都向前移動(dòng)了一位,所以i也向前移動(dòng)一位 size--; } } return size; } }
思路2:雙指針法
分別設(shè)設(shè)一個(gè)快慢指針,slow fast ,兩者一起走,當(dāng)慢指針遇到要?jiǎng)h除的元素時(shí)停下,等待著被刪除(覆蓋);當(dāng)快指針走到要被留下的元素時(shí),將快指針的元素賦值給慢指針,然后兩指針同時(shí)向后走,直到快指針遍歷完整個(gè)數(shù)組。
可以這么理解:定義數(shù)組的新長(zhǎng)度newLength ,從0開始,定義一個(gè)快指針遍歷數(shù)組 fast,當(dāng)fast走到要被留下的元素時(shí),說明該元素應(yīng)該被添加到新數(shù)組中(即被添加到newLength 下標(biāo),這里相當(dāng)于 newLength 之前的部分?jǐn)?shù)組看做要返回的新數(shù)組,相當(dāng)于往這個(gè)新數(shù)組里插入元素)。
class Solution { public int removeElement(int[] nums, int val) { int fast = 0;// 定義一個(gè)快指針遍歷數(shù)組 int newLength = 0;// 定義新的數(shù)組長(zhǎng)度 while(fast < nums.length){ if(nums[fast] != val){ nums[newLength++] = nums[fast]; } fast++; } return newLength; } }
推薦力扣題目
其他常見數(shù)組的考點(diǎn)很多都是以這兩點(diǎn)為基礎(chǔ),無非就是對(duì)數(shù)組增刪改查,將數(shù)組的查找和刪除掌握了,就可以開始刷題啦。
到此這篇關(guān)于Java 數(shù)組高頻考點(diǎn)分析講解的文章就介紹到這了,更多相關(guān)Java 數(shù)組內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringCloud Gateway使用redis實(shí)現(xiàn)動(dòng)態(tài)路由的方法
這篇文章主要介紹了SpringCloud Gateway使用redis實(shí)現(xiàn)動(dòng)態(tài)路由的方法,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-01-01Java基于自定義類加載器實(shí)現(xiàn)熱部署過程解析
這篇文章主要介紹了Java基于自定義類加載器實(shí)現(xiàn)熱部署過程解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03mybatis實(shí)現(xiàn)獲取入?yún)⑹荓ist和Map的取值
這篇文章主要介紹了mybatis實(shí)現(xiàn)獲取入?yún)⑹荓ist和Map的取值問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-06-06Java編程一個(gè)隨機(jī)數(shù)產(chǎn)生模塊代碼分享
這篇文章主要介紹了Java編程一個(gè)隨機(jī)數(shù)產(chǎn)生模塊代碼分享,具有一定借鑒價(jià)值,需要的朋友可以參考下。2017-12-12