有序数组的增删改查-蒲公英云

有序数组的增删改查

女爷i 2024-03-26 19:03 112阅读 0赞

public class ArrDemo {
     private int[] arr = new int[20];
     private int flag = 0;
     public void add(int x){
          System.out.print("插入的新数据:" +x+" ");
          if(flag==arr.length){
               int[]  arrNew = new int[arr.length*2];
               for (int i = 0;i< arrNew.length;i++){
                    arrNew[i]=arr[i];
               }
               arr=arrNew;
          }
          //找到插入的正确位置
          if(flag==0){
               arr[0]=x;
               flag++;
               return;
          }
          int insertIndex=getInsertIndex(x);
          for(int i = flag;i>insertIndex;i--){
               arr[i] = arr[i-1];
          }
          flag++;
          arr[insertIndex]=x;
     }
     public int getIndex(int x){
          int left = 0;
          int right = arr.length-1;
          while (left<=right){
               int middle = (left+right)/2;
               if (arr[middle]==x){
                    return middle;
               }else if(arr[middle]<x){
                    left=middle+1;
               }else {
                    right=middle-1;
               }
          }
          return -1;
     }
     //有序数组要插入的位置
     public int getInsertIndex(int x){
          int left = 0;
          int right = flag-1;
          while (left <= right){
               int middle = (left+right)/2;
               if (arr[middle]==x){
                    return middle;
               }else if(arr[middle]<x){
                    left=middle+1;
               }else {
                    right=middle-1;
               }
          }
          int middles = (left+right)/2;  //防止右侧越界
          if(arr[middles] >= x){
               return middles;
          }else{
               return middles+1;
          }
     }
     public void change(int oldNum,int newNum){
          int index = getIndex(oldNum);
          arr[index]=newNum;
     }
     public void del(int x){
          int index = getIndex(x);
          for (int i =index;i<flag-1;i++){
               arr[i]=arr[i+1];
          }
          flag--;
     }
     public void show(){
          for (int i =0;i<flag;i++){
               System.out.print("arr["+i+"]:"+arr[i]+" ");
          }
     }

测试：

public class ArrTest {
    public static void main(String[] args) {
        ArrDemo arrDemo = new ArrDemo();
       arrDemo.add(1);arrDemo.add(8);arrDemo.add(9999);arrDemo.add(12);
        arrDemo.add(5);arrDemo.add(55);arrDemo.add(-14);arrDemo.add(666);
        System.out.println("--------------------------------");
        arrDemo.show();
    }
}