問(wèn)題描述

已知長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫(xiě)一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。

void Delete（ElemType A[ ]，int n）∥A是有n個(gè)元素的一維數(shù)組，本算法刪除A中所有值為item的元素。{i=1；j=n；∥設(shè)置數(shù)組低、高端指針（下標(biāo)）。 while（i<j） {while（i<j && A[i]!=item）i++； ∥若值不為item，左移指針。 if（i<j）while（i<j && A[j]==item）j--；∥若右端元素為item，指針左移 if（i<j）A[i++]=A[j--]；}

改寫(xiě)之后運(yùn)行不出來(lái)，下面是改寫(xiě)后的

package 線性表;public class Work_10 { public Work_10(){int[] arr={2,34,4,4,5};int item=4;delete(arr,item,arr.length-1);for(int a:arr){ System.out.print(a+' ');} } public static void delete(int[] array,int item,int n){int i=0,j=n;while(i<j){ while(i<j&&array[i]!=item) i++; if(i<j) while(i<j&&array[j]==item) j--; if(i<j){array[i++]=array[j--]; }} } public static void main(String[] args) {new Work_10(); }}

不知道該怎么改？求大佬解釋

問(wèn)題解答

要想刪除，先搜索，后刪除，給你個(gè)搜索的，剩下的自己思考下寫(xiě)個(gè)變種就可以了。

public static int search(byte[] a,int n, byte item) {int low = 0;int high = n - 1;while (low <= high) { int mid = (low + high) >>> 1; byte midVal = a[mid]; if (midVal < item)low = mid + 1; else if (midVal > item)high = mid - 1; elsereturn mid; // 找到item}return -(low + 1); // 沒(méi)找到item }回答2：

哦，多出來(lái)是因?yàn)槟爿敵龅膫€(gè)數(shù)錯(cuò)了，刪除的過(guò)程沒(méi)問(wèn)題。

刪除前，你的數(shù)組內(nèi)容是 2,34,4,4,5，共 5 個(gè)元素。

要?jiǎng)h除的內(nèi)容為 4，也就是說(shuō)刪除后只剩 3 個(gè)元素，分別是 2,34,5

所以你的結(jié)果輸出只需要輸出數(shù)組的前 3 個(gè)，后面那兩個(gè)是作廢了的元素。