移除数组元素双指针法（蓝桥杯练习2java)

雨点打透心脏的1/2处 2023-10-10 16:13 35阅读 0赞

蓝桥杯练习2

力扣27 ：移除数组元素。

练习目的：理解数组的数据存储原理，只能覆盖数据，空间无法移除。理解双指针法降低时间复杂度

时间复杂度：O（n^2）.空间：O(1)

解题思路：

难点：要求空间复杂度为O(1),不能开辟另外的空间

class Solution {
        
        public int removeElement(int[] nums, int val) {
        
           //移除数组中的目标值，也就是将后面的值覆盖目标值，暴力解法
           int flag = nums.length;
           //1.遍历整个数组
           for(int i = 0;i<nums.length ;i++){
        
               if(nums[i] == val) {
        
                   //2.找到一个长度减一
                   flag--;
                   //3.覆盖要删除的数据
                   for(int j = i + 1;j<nums.length ;j++){
        
                   nums[i] = nums[j];
                   }
                   //4.移除nums[i]后需要继续判断i位置覆盖过来的数据
                   i--;
               }
           }
           return flag;
        }
    }

优化解法：双指针法（属于快慢指针法）

方向思考，他要清理目标值，可以将非目标值取出。

class Solution {
        
        public int removeElement(int[] nums, int val) {
        
            // 优化解法，双指针解法
            // 1.定义两个指针
            int head = 0;
            // 2.移动指针，先移动头指针，i 是快指针
            for(int i = 0;i<nums.length;i++){
        
                if(val != nums[i]){
        
                    // 3.将非目标值存起来，依然存在原来的数组里
                    nums[head++] = nums[i]; 
                }
            }
            return head;
        }
    }

--------------------