首页 >社区问答列表 >java - 求下面这道算法的解释

java - 求下面这道算法的解释

已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。

void  Delete(ElemType A[ ],int  n)
∥A是有n个元素的一维数组,本算法删除A中所有值为item的元素。
{i=1;j=n;∥设置数组低、高端指针(下标)。
 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--];}

改写之后运行不出来,下面是改写后的

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();
    }
}

不知道该怎么改?
求大佬解释

  • 淡淡烟草味
  • 淡淡烟草味    2017-07-05 10:28:052楼

    要想删除,先搜索,后删除,给你个搜索的,剩下的自己思考下写个变种就可以了。

    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;
                else
                    return mid; // 找到item
            }
            return -(low + 1); // 没找到item
        }

    +0添加回复

  • 回复
  • 世界只因有你
  • 世界只因有你    2017-07-05 10:28:051楼

    哦,多出来是因为你输出的个数错了,删除的过程没问题。

    删除前,你的数组内容是 2,34,4,4,5,共 5 个元素。

    要删除的内容为 4,也就是说删除后只剩 3 个元素,分别是 2,34,5

    所以你的结果输出只需要输出数组的前 3 个,后面那两个是作废了的元素。

    +0添加回复

  • 回复