面试通关村——不简单的数组增删改查

野性酷女 2024-02-21 12:28 36阅读 0赞

public class Array {
        /**
         * 查找1.0
         * @param arr
         * @param size
         * @param key
         * @return
         */
        //查找一个元素
        public static int findByElement(int[] arr,int size,int key){
            for(int i=0;i<size;i++){
                if(arr[i]==key)
                    return i;
            }
            //如果没找到
            return -1;
        }
        /**
         * 查找2.0
         * @param arr
         * @param size
         * @param key
         * @return
         */
        //如果数组是递增的，此时查找时如果相等或者当前位置元素比目标值更大就停下了。
        //递增数组查找
        public static int findIncrementalArrayByElemnt(int[] arr,int size,int key){
            for(int i=0;i<size||arr[i]>key;i++){
                if(arr[i]==key)
                    return i;
            }
            return -1;
        }
        //增加一个元素，能够正确处理游标和边界等情况是数组算法题最基础重要的问题之一。先找位置，将其后元素整体右移，
        //最后插入到空位置上，需要保证在首部，尾部和中间位置都可以插入成功
        /**
         *插入1.0
         * @param arr
         * @param size 数组已经存储的元素数量，从1开始编号
         * @param element 待插入的元素
         * @return
         */
        public static int addByElementSequence(int[] arr,int size,int element){
            //如果size>arr.length，那么就相当于刚好数组已满的情况下允许插入，此时已经存储的元素数量=数组1长度，
            //但再插入一个size++，就会越界。
            if(size>=arr.length)
                return -1;
    
            //找到新元素插入的位置
            //这里，index实际上时提前预设element大于已存所有元素，那么就插到尾部，此时已经存储元素就要+1，下标就为size。
            //当原来已存元素是size,那么最大元素下标是size-1；新插入元素后size++，那么此时最大元素下标就是size
            int index=size;
            //左闭右开区间，实际上执行size次，由于size从1开始，i=0时，指向第一个元素，i=size-1，即i<size时，指向最后一个元素。
            for(int i=0;i<size;i++){
                if(element<arr[i]) {
                    index = i;
                    break;
                }
            }
    
            //元素后移,先将最后一个元素后移，然后倒数第二个...
            //这里可以想一下最后一个元素后移，这个元素作为最后的数，原来下标为size-1（size从1计数，始终比下标多1）
            // 那么新下标就是size，结合arr[j]=arr[j-1]，所以你j最大为最后一个元素的下标size.
            //j最小是index+1,也就是要最后一个元素要挪的下标为index+1.
            for(int j=size;j>index;j--){
                arr[j]=arr[j-1];//右赋值，index下标开始的元素后移一个位置
            }
    
            //插入元素
            arr[index]=element;
            return index;
        }
    
        /**
         * 插入2.0
         * @param arr
         * @param size
         * @param element
         * @return
         */
        //还可以一开始从后向前一百年移动一遍对比查找，找到位置直接插入。从效率上看这样更好一些，因为只遍历了一次。
        public static int myAddByElementSequence(int[] arr,int size,int element){
            return 0;
        }
    
        /**
         * 删除元素
         * @param arr
         * @param size
         * @param key
         * @return
         */
        //删除元素，不能一边从后向前移动一边查找，因为元素可能不存在。所以要分为两个步骤，先从最左侧开始查是否存在元素
        //如果元素存在，那么从该位置开始执行删除操作，也就是从下一位开始逐步覆盖上一个元素。
        //1 2 3 4 5 6 7 8 9->删除5->1 2 3 4 6 7 8 9 【9】
        //因为通过size来标记元素数量，所以最后9不会被访问到，不必优化。
        public int removeByElement(int[] arr,int size,int key){
            //提前标记循环不会进入if的情况，即元素不存在。所以index=-1；
            int index=-1;
            for(int i=0;i<size;i++){
                if(arr[i]==key){
                    index=i;
                    break;
                }
            }
            //如果元素存在
            if(index!=-1){
                //i最小是索引后一个位置，最大是最后一个元素下标即size-1；
                for(int i=index+1;i<size;i++){
                    arr[i-1]=arr[i];//右赋值，搞清楚赋值方向。
                    size--;
                }
            }
            return size;
        }
    
        /**
         * 单调数组1.0
         * @param nums
         * @return
         */
        //如果对于所有的i<=j;A[i]<=A[j]，那么A单调递增;A[i]>=A[j]，，那么A单调递减,执行两次循环
        public boolean isMonotonic(int[] nums){
            return isSorted(nums,true)||isSorted(nums,false);
        }
        public boolean isSorted(int[] nums,Boolean increasing) {
            int n = nums.length;
            for (int i = 0; i < n - 1; i++) {
                if (increasing) {
                    if (nums[i] > nums[i + 1]) {
                        return false;
                    }
                } else {
                    if (nums[i] < nums[i + 1]) {
                        return false;
                    }
                }
            }
            return true;
        }
    
        /**
         *单调数组2.0
         * @param nums
         * @return
         */
        //如果在i和i+1的位置出现了nums[i]>nums[i+1],而另外一个地方出现了nums[j]<nums[j+1]，则说明不单调。
        public boolean reIsMonotonic(int[] nums){
            boolean inc =true,dec=true;
            int n= nums.length;
            for(int i=0;i<n-1;i++){
                if(nums[i]>nums[i+1]){
                    inc=false;
                }
                if(nums[i]<nums[i+1]){
                    dec=false;
                }
            }
            return inc||dec;
        }
        //给你两个按非递减顺序排列的有序整数数组nums1和nums2,另外有两个整数m和n，分别表示nums1和nums2的元素数组。请你合并nums2到nums1中
        //使合并后的数组同样按非递减顺序排列
        //注意：合并后数组存储在nums1中，nums1初始长度应该为m+n
        //比较好的方式是从后向前插入，A和B的元素数量是固定的，所以排序后最远位置一定是A和B元素都最大的那个
        // ，依次类推，每次都找到最大的那个从后向前填就可以了
        public void merge(int[] nums1,int nums1_len,int[] nums2,int nums2_len){
            int i=nums1_len+nums2_len;
            int len1=nums1_len-1,len2=nums2_len;
            while(len1>=0&&len2>=0){
                if(nums1[len1]<=nums2[len2])
                     nums1[i--]=nums2[len2--];
                else if(nums1[len1]>nums2[len2])
                    nums1[i--]=nums1[len1--];
            }
            //假如A和B数组还有剩余
            while(len2!=-1)nums1[i--]=nums2[len2--];
            while(len1!=-1)nums1[i--]=nums1[len1--];
        }
    }