【基本数据结构】三、基本的数据结构

短命女 2023-10-09 14:28 12阅读 0赞

上一篇[【二进制和位运算】二、认识时间复杂度][Link 1]

#### 文章目录 ####

*  基本的数据结构
 *   *  1、数组
     *   *  1.1、特点：一片连续的内存空间，所以查询遍历效率高，增删尾部的元素效率也高，但是随机增删元素效率低。
         *  1.2、各个操作的时间复杂度：检索：O(1)、新增：O(n)、删除：O(n)
     *  2、链表
     *   *  2.1、特点：上一个节点持有下一个节点的引用，所以增删效率高，但是检索元素效率低。
         *  2.2、各个操作的时间复杂度：检索：O(n)、新增：O(1)、删除：O(1)
         *  2.3、在实际工作中的应用举例：LRU cache（最近最少使用的）算法就是通过链表实现的。
     *  3、经典算法
     *   *  3.1 、力扣第283题： 将所有的0移动到数组的末尾
         *  3.1 、力扣第26题 删除排序数组中的重复项
         *  3.3、力扣第189题：

## 基本的数据结构 ##

### 1、数组 ###

#### 1.1、特点：一片连续的内存空间，所以查询遍历效率高，增删尾部的元素效率也高，但是随机增删元素效率低。 ####

#### 1.2、各个操作的时间复杂度：检索：O(1)、新增：O(n)、删除：O(n) ####

### 2、链表 ###

#### 2.1、特点：上一个节点持有下一个节点的引用，所以增删效率高，但是检索元素效率低。 ####

#### 2.2、各个操作的时间复杂度：检索：O(n)、新增：O(1)、删除：O(1) ####

#### 2.3、在实际工作中的应用举例：LRU cache（最近最少使用的）算法就是通过链表实现的。 ####

### 3、经典算法 ###

#### 3.1 、力扣第283题： 将所有的0移动到数组的末尾 ####

/**
     * 力扣第283题：
     * https://leetcode-cn.com/problems/move-zeroes/
     * 
     * 将所有的0移动到数组的末尾
     */
    public class LeetCodeTest01 {
        
    
    	public static void main(String[] args) {
        
    	    
    	    //准备数据
    	    int[] arr = {
        4,2,4,0,0,3,0,5,1,0};//预期结果：4,2,4,3,5,1,0,0,0,0
    //	    int[] arr = {0,1,0,3,12};
    //	    int[] arr = {0,0,1};
    	    
    	    
    	    System.out.println("移动零前的数组："+Arrays.toString(arr));
    	    
    	    //方法1：写两层循环
    //	    moveZero1(arr);
    	    //方法2：新开一个数组将所有的0依次放到新数组的末尾
    //	    moveZero2(arr);
    	    
    	    //方法3：一层循环，做下标移动
    	    moveZero3(arr);
    	    System.out.println("移动零后的数组："+Arrays.toString(arr));
    
    	}
    
        /**
         * 仅仅是使用一个变量去记录非0元素
         * 最后需要存放的位置，然后遍历过程中
         * 交换即可。
         * 时间复杂度：O(n)
         * 空间复杂度：O(1)
         * @param arr   需要处理的数组
         */
        private static void moveZero3(int[] arr) {
        
            //用于记录非0元素的下标
            int j = 0;
            for (int i = 0; i < arr.length; i++) {
        
                //如果为0就跳过，我们只处理非0元素
                if(arr[i] == 0){
        
                    continue;
                }
                //将非0元素和0的下标位置进行交换
                int tmp = arr[i] ^arr[j];
                arr[i] ^= tmp;
                arr[j] ^= tmp;
                j++;
            }
            
        }
        
        
    
        /**
         * 使用新开一个数组的方法实现
         * 与题目要求不相符，题目要求不能新开辟一个其它数组，
         * 只能在原有数组上进行操作。
         * 时间复杂度：O(n)
         * 空间复杂度：O(n)
         * @param arr   需要处理的数组
         */
        private static void moveZero2(int[] arr) {
        
            
            int[] result = new int[arr.length];
            
            for (int i = 0,j=0; i < arr.length; i++) {
        
                //如果为0就跳过
                if(arr[i] == 0){
        
                    continue;
                }
                
                //将非0数放到新数组的前面
                result[j] = arr[i]; 
                j++;
                
            }
            
            //将结果数组复制到入参中
           System.arraycopy(result, 0, arr, 0, result.length);
            
            
        }
    
        /**
         * 使用嵌套for循环方式实现
         * 时间复杂度：O(n^2)
         * 空间复杂度：O(1)
         * @param arr   需要处理的数组
         */
        private static void moveZero1(int[] arr) {
        
            
            int zeroCount = 0;
            for (int i = 0; i < arr.length; i++) {
        
    	        //如果不为0就跳过本次循环
    	        if(arr[i] != 0){
        
    	            continue;
    	        }
    	        zeroCount++;
    	        if(i+1 < arr.length && arr[i+1] == 0){
        
    	            continue;
    	        }
    	        
                /*
                 * 如果为0就将其删除：将后面的元素往前挪
                 * 有多少个0就挪多少位
                 */
    	        for (int j = i+1; j < arr.length; j++) {
        
    	            //将后面的元素往前挪的操作
                    arr[j-zeroCount] = arr[j]; 
                }
    	        
    	        for (int j = 1; j <= zeroCount; j++) {
        
    	            arr[arr.length-j] = 0;
                }
    	        
    	        /*
    	         * 移位之后需要将外层的循环变量重置到
    	         * 移动0后的起始位的下一位开始，
    	         * 否则会导致移位后的0没有被处理，
    	         * 如果不加1就会导致死循环
    	         */
    	        i = i - zeroCount + 1;
    	        
    	        zeroCount = 0;
            }
        }
    
    }

#### 3.1 、力扣第26题 删除排序数组中的重复项 ####

/**
     * 力扣第26题：
     * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
     * 
     * 删除排序数组中的重复项
     */
    public class LeetCodeTest02 {
        
    
    	public static void main(String[] args) {
        
    		//准备数据
    //	    int[] arr = {1,1,2};
    	    int[] arr = {
        0,0,1,1,1,2,2,3,3,4};
    	    System.out.println("处理前的数组："+Arrays.toString(arr));
    	    //方法1：穷举
    //	    int length = removeDuplicates1(arr);
    	    
    	    //方法2：另外开辟一个空间去判断
    //	    int length = removeDuplicates2(arr);
    	    //方法3：双指针
    	    int length = removeDuplicates3(arr);
    	    System.out.println("处理后的数组："+Arrays.toString(arr) +"长度为："+ length);
    	    
    	    System.out.println("处理后的数组："+ArrayUtils.toString(arr, 0, length));
    
    	}
    
    	/**
    	 * 双指针法：
    	 * 注意：这个前提是这个数组是已经排好序了
    	 * 时间复杂度为：O(n)
    	 * 空间复杂度为：O(1)
         * @param arr   需要处理的数组
         * @return  处理后的数组的长度
         */
        private static int removeDuplicates3(int[] arr) {
        
            //定义一个变量用于记录最后一个不重复元素的下标
            int i = 0;
            //从第二个元素开始遍历数组
            for (int j = 1; j < arr.length; j++) {
        
                //当i下标的值和j下标的值相同时就跳过本次循环
                if(arr[i] == arr[j]){
        
                    continue;
                }
                /*
                 * 当i下标的值和j下标的值不同时
                 * 就让i往后移1位后交换下标i和j的值
                 */
                i++;
                arr[i] = arr[j];
            }
            //最后返回最后一个不重复元素的下标+1就是数组的长度
            return i + 1;
        }
    
        /**
    	 * 另外开辟一个数组空间进行处理方式
    	 * 虽然使用了两个for循环，但是两个for循环是并列关系
    	 * 所以时间复杂度：O(n)
    	 * 但是不符合题意的要求不能另外开辟数组空间
    	 * 由于另外开辟了一个数组空间，所以空间复杂度为：O(n)
         * @param arr   需要处理的数组
         * @return  处理后的数组的长度
         */
        private static int removeDuplicates2(int[] arr) {
        
    
            //由于需要保证有序所以使用LinkedHashSet
            Set<Integer> arrSet = new LinkedHashSet<>();
    
            //遍历数组将其每一个元素装进Set中
            for (int i = 0; i < arr.length; i++) {
        
                arrSet.add(arr[i]);
            }
            
            //再将Set中的元素装回数组中
            Object[] array = arrSet.toArray();
            for (int i = 0; i < array.length; i++) {
        
                arr[i] = (int)array[i];
            }
            
            return array.length;
        }
    
        /**  
    	 * 暴力方式：穷举
    	 * 由于使用了3层循环，所以
    	 * 时间复杂度：O(n^3)
    	 * 空间复杂度：O(1)
    	* @param arr	需要处理的数组
    	* @return	处理后的数组的长度
    	*/  
    	private static int removeDuplicates1(int[] arr) {
        
    		//新数组的长度：假设所有元素都不重复则为原数组长度
    		int length = arr.length;
    		
    		/*
    		 * 遍历数组
    		 * 注意：如果已经到了最后一个元素，那么肯定没有重复的了
    		 * 所以不用遍历最后一个元素，因此是arr.length - 1
    		 */
    		for (int i = 0; i < length - 1; i++) {
        
    			//从下一个元素开始查找是否有相等的
    			for (int j = i+1; j < length; j++) {
        
    				//如果不相等说明不是重复的元素，跳过本次循环
    				if(arr[i] != arr[j]){
        
    					continue;
    				}
    				//然后将之后的元素都往前挪一位
    				for (int k = j; k < length - 1; k++) {
        
    					arr[k] = arr[k+1];
    				}
    				//如果相等说明有重复的元素，就让length自减1
    				length--;
    				/*
    				 * 由于进行了往前挪一位，所以需要重置j的位置到j-1
    				 * 从j-1位置继续往后比较
    				 */
    				j--;
    			}
    //			System.out.println("第"+(i+1)+"次循环的数组："+Arrays.toString(arr));
    		}
    		
    		return length;
    	}
    
    }

#### 3.3、力扣第189题： ####

/**
     * 力扣第189题：
     * https://leetcode-cn.com/problems/rotate-array/
     * 旋转数组
     * @author Peter
     */
    public class LeetCodeTest03 {
        
    
    	public static void main(String[] args) {
        
    	    //准备数据
    	    int[]  arr = {
        1,2,3,4,5,6,7};
    	    
    	    int k = 3;
    	    System.out.println("处理前的数组："+Arrays.toString(arr));
    //	    rotate1(arr,k);
    //	    rotate2(arr,k);
    //	    rotate3(arr,k);
    	    rotate4(arr,k);
    	    System.out.println("处理后的数组："+Arrays.toString(arr));
    	}
    
        /**
         * 暴力方式：嵌套循环将每个元素依次往后挪
         * 总共挪k次，就是往后挪了k位
         * 由于使用了嵌套循环所以
         * 时间复杂度为：O(k*n) 
         * 空间复杂度为：O(1)
         * @param arr   需要处理的数组
         * @param k     需要往后移动的位数
         */
        private static void rotate1(int[] arr, int k) {
        
            
            //排除特殊情况
            if(arr == null || arr.length <=1){
        
                return;
            }
            
            //由于需要往后挪k位，所以需要循环k次
            for (int i = 0; i < k; i++) {
        
                //声明一个临时变量用于记录被覆盖的数
                int tmp = 0;
                //用于保存上一个数的变量
                int previous = arr[0];
                //往后挪1位
                for (int j = 0; j < arr.length ; j++) {
        
                    //如果是最后一个元素就直接放到第一个下标上去
                    if(j == arr.length-1){
        
                        arr[0] = tmp;
                        continue;
                    }
                    tmp = arr[j+1];
                    arr[j+1] =previous;
                    previous = tmp;
                }
            }
        }
        
        
        /**
         * 另外开辟一个数组空间进行处理方式
         * 
         * 时间复杂度为：O(n) 
         * 由于使用了额外的数组空间所以
         * 空间复杂度为：O(n)
         * @param arr   需要处理的数组
         * @param k     需要往后移动的位数
         */
        private static void rotate2(int[] arr, int k) {
        
            
            //用一个数组去存放旋转后的结果
            int[] resultArr = new int[arr.length];
            
            //首先将数组中的元素放到其旋转后正确的位置
            for (int i = 0; i < arr.length; i++) {
        
                //使用取模的方式去处理下标越界的问题
                resultArr[(i+k) % resultArr.length] = arr[i];
            }
            
            //不能这样，因为Java是值传递的
    //        arr = resultArr;
            
            //然后将处理好的数组复制到原数组中
            System.arraycopy(resultArr, 0, arr, 0, arr.length);
            
        }
        
        
        /**
         * 环状替换方式，易于理解参考：
         * https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-yuan-di-huan-wei-xiang-xi-tu-jie/
         * 时间复杂度为：O(n) 
         * 空间复杂度为：O(1)
         * @param arr   需要处理的数组
         * @param k     需要往后移动的位数
         */
        private static void rotate3(int[] arr, int k) {
        
            
            //如果k > arr.length 那么其移动的步数就为其取余arr.length后的步数
            k %= arr.length;
            // 记录交换位置的次数，n个同学一共需要换n次
            int count = 0;         
            //对每一个元素将其放到最后的位置
            for(int i = 0; count < arr.length; i++) {
        
                int cur = i;       // 从0位置开始换位子
                do{
        
                    //得到其应该存放的下标
                    int next = (cur + k) % arr.length;
                    //先保存一下要被替换的下标的值
                    int temp = arr[next];    // 来到角落...
                    //开始交换
                    arr[next] = arr[i];
                    arr[i] = temp;
                    //下一次循环从被挤走的数的下标开始
                    cur = next;
                    count++;
                }while(i != cur)  ;     // 循环暂停，回到起始位置，角落无人
                 
            }   
        }
        
        /**
         * 反转方法实现
         * 
         * 时间复杂度为：O(n) 
         * 空间复杂度为：O(1)
         * @param arr   需要处理的数组
         * @param k     需要往后移动的位数
         */
        private static void rotate4(int[] arr, int k) {
        
            //首先反转整个数组
            reverse(arr, 0, arr.length-1);
            //然后反转前(k取余arr.length)个数
            k %= arr.length;
            reverse(arr, 0, k-1);
            //再反转后面n-k个数即可得到最终结果
            reverse(arr, k, arr.length-1);
        }
        
        /**
         * 反转数组的方法
         * @param arr   需要被反转的数组
         * @param start 需要被反转的起始下标
         * @param end   需要被反转的结束下标
         */
        private static void reverse(int[] arr, int start, int end) {
        
            /*
             * 当左下标小于右下标时不断交换两个数
             * 当交换完毕之后整个数组就达到了反转的效果
             */
            while (start < end) {
        
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
                //两边指针不断往中间靠
                start++;
                end--;
            }
        }
    
        
    }

[Link 1]: https://blog.csdn.net/weixin_43333483/article/details/125627057