資訊專欄INFORMATION COLUMN
摘要：主要是因?yàn)閿?shù)組已經(jīng)是排好順序的。如果不仔細(xì)看題目，把數(shù)組當(dāng)作無(wú)序數(shù)組進(jìn)行操作，時(shí)會(huì)顯示超時(shí)。題目要求是不能申請(qǐng)二額外空間，如果提交時(shí)有申請(qǐng)額外空間，也是不通過(guò)的。比如對(duì)于數(shù)組，移除重復(fù)元素后為，起始數(shù)字為，而不能是其它數(shù)字。
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].
思路：
（1）這道題其實(shí)很簡(jiǎn)單。主要是因?yàn)閿?shù)組已經(jīng)是排好順序的。如果不仔細(xì)看題目，把數(shù)組當(dāng)作無(wú)序數(shù)組進(jìn)行操作，OJ時(shí)會(huì)顯示超時(shí)。
（2）題目要求是不能申請(qǐng)二額外空間，如果提交時(shí)有申請(qǐng)額外空間，也是不通過(guò)的。
（3）還需要注意的一個(gè)地方是，數(shù)組中元素的位置不能改變。比如對(duì)于數(shù)組[1,1,1,4,5]，移除重復(fù)元素后為[1,4,5]，起始數(shù)字為1，而不能是其它數(shù)字。
（4）我們只需對(duì)對(duì)組遍歷一次，并設(shè)置一個(gè)計(jì)數(shù)器，每當(dāng)遍歷前后元素不相同，計(jì)數(shù)器加1，并將計(jì)數(shù)器對(duì)應(yīng)在數(shù)組中位置定位到當(dāng)前遍歷的元素。
算法代碼實(shí)現(xiàn)如下：
public static int removeDuplicates(int[] A) {
int len = A.length;
if (len == 0)
return 0;
int count = 1;
for (int i = 1; i < len; i++) {
if (A[i] == A[i - 1]) {
continue;
}else{
A[count] = A[i];
count++;
}
}
return count;
}
上面的解法是針對(duì)有序數(shù)組，如果是無(wú)序數(shù)組，應(yīng)該如何解答？
思路：
（1）如果不允許申請(qǐng)額外空間，則可以先對(duì)數(shù)組進(jìn)行排序，為了提高效率一般考慮使用快速排序，然后再參照上面有序數(shù)組進(jìn)行操作；
（2）如果允許申請(qǐng)空間，則只需創(chuàng)建一個(gè)HashSet，遍歷一次數(shù)組，通過(guò)contanins()方法進(jìn)行判斷就能得到結(jié)果。
（1）和（2）所對(duì)應(yīng)代碼如下所示（注：針對(duì)本文所示的題目，如果用下面代碼進(jìn)行OJ，（1）會(huì)超時(shí)，（2）會(huì)產(chǎn)生額外空間）：
不可以申請(qǐng)額外空間：
public static int removeDuplicates(int[] A) {
int len = A.length;
if (len == 0)
return 0;
quickSort(A, 0, len - 1);
int count = 1;
for (int i = 1; i < len; i++) {
if (A[i] == A[i - 1]) {
continue;
} else {
A[count] = A[i];
count++;
}
}
return count;
}
//快速排序
private static void quickSort(int[] table, int low, int high) {
if (low < high) {
int i = low, j = high;
int vot = table[i];
while (i != j) {
while (i < j && vot <= table[j])
j--;
if (i < j) {
table[i] = table[j];
i++;
}
while (i < j && table[i] < vot)
i++;
if (i < j) {
table[j] = table[i];
j--;
}
}
table[i] = vot;
quickSort(table, low, j - 1);
quickSort(table, i + 1, high);
}
}
可以申請(qǐng)額外空間：（其中，HashSet的contains()方法是用來(lái)過(guò)濾重復(fù)元素的）
public static int removeDuplicates(int[] A) {
int len = A.length;
HashSet set = new HashSet();
for (int i = 0; i < len; i++) {
if (set.size() == 0) {
set.add(A[i]);
}
if (!set.contains(A[i])) {
set.add(A[i]);
}
}
return set.size();
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66422.html
摘要：雙指針法復(fù)雜度時(shí)間空間思路我們可以將不重復(fù)的序列存到數(shù)列前面，因?yàn)椴恢貜?fù)序列的長(zhǎng)度一定小于等于總序列，所以不用擔(dān)心覆蓋的問(wèn)題。代碼雙指針法復(fù)雜度時(shí)間空間思路思路和上題一樣，區(qū)別在于記錄前兩個(gè)遍歷到的數(shù)字來(lái)幫助我們判斷是否出現(xiàn)了第三遍。 Remove Duplicates from Sorted Array I Given a sorted array, remove the dupl...
摘要：思路原數(shù)組長(zhǎng)度為，則返回原數(shù)組長(zhǎng)度不為，則至少有個(gè)元素。將所有不重復(fù)的數(shù)值賦給，而當(dāng)和相等時(shí)，不做處理。最后返回的就是不同元素的個(gè)數(shù)，也是新數(shù)組的長(zhǎng)度。只有在時(shí)，才對(duì)賦值。注意，每次初始化的時(shí)候要分兩種情況，這就意味著從的時(shí)候開始遍歷。 Remove Duplicates from Sorted Array I Problem Given a sorted array, remove ...
摘要：題目比較簡(jiǎn)單，就是找出數(shù)組不重復(fù)的數(shù)字，返回不重復(fù)的數(shù)字個(gè)數(shù)。無(wú)需刪除重復(fù)數(shù)字，只需要保證數(shù)組的前位為不重復(fù)的個(gè)數(shù)字即可代碼如下 Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not all...
摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用額外空間的條件下完成。聲明兩個(gè)指針，為快指針，為慢指針如果遇到相同的數(shù)，那么就跳過(guò)，。 給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組...
閱讀 2194·2021-11-24 09:38
閱讀 3255·2021-11-08 13:27
閱讀 3095·2021-09-10 10:51
閱讀 3162·2019-08-29 12:20
閱讀 674·2019-08-28 18:28
閱讀 3470·2019-08-26 11:53
閱讀 2718·2019-08-26 11:46
閱讀 1527·2019-08-26 10:56
