首页 > 其他分享 >LeetCode | 27 RemoveElement

LeetCode | 27 RemoveElement

时间:2024-07-31 21:39:34浏览次数:17  
标签:27 val nums int RemoveElement result LeetCode left

https://github.com/dolphinmind/datastructure/tree/datastructure-array

主类

package com.github.dolphinmind.array.binarysearch;

/**
 * @author dolphinmind
 * @ClassName RemoveElement
 * @description 27 移除元素
 *              移除元素分析
 *              快慢指针
 *              双向指针
 *              slow和left指针都处于有效数组的末尾,即不包含var的元素的最后一个位置之后,返回的slow和left即有效数组的长度
 * @date 2024/7/31
 */

public class RemoveElement {

    private int left;
    private int right;

    /**
     * 快慢指针同向
     *      slow 处于有效数组的末尾,即不包含target的元素的最后一个位置之后,返回的left即有效数组的长度
     * 
     * @param nums
     * @param val
     * @return
     */
    public int removeElementTwoPointersCoextensive(int[] nums, int val) {
        int slow = 0;
        int fast = 0;

        while (fast < nums.length) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }

            fast++;
        }

        return slow;
    }

    /**
     * 双指针反向:左指针 右指针 while边界问题也符合开闭原则:左闭右开
     * 疑惑:双指针如果left==right的时候,nums[left] == val,这时返回
     *      left 处于有效数组的末尾,即不包含target的元素的最后一个位置之后,返回的left即有效数组的长度
     * 
     * @param nums
     * @param val
     * @return
     */
    public int removeElementTowPointersReverse1(int[] nums, int val) {
        left = 0;
        right = nums.length - 1;

        while (left <= right) {
            if (nums[left] == val) {
                nums[left] = nums[right];
                right--;
            } else {
                left++;
            }
        }

        if (nums[left] == val) {
            return left - 1;
        }

        return left;
    }

    /**
     * 左闭右闭
     * @param nums
     * @param val
     * @return
     */
    public int removeElementTowPointersReverse2(int[] nums, int val) {
        left = 0;
        right = nums.length;

        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }

        return left;
    }
}

测试类

package com.github.dolphinmind.array.binarusearch;

import com.github.dolphinmind.array.binarysearch.RemoveElement;
import org.junit.Test;

/**
 * @author dolphinmind
 * @ClassName RemoveElementTest
 * @description
 * @date 2024/7/31
 */

public class RemoveElementTest {

    /**
     * 测试同向快慢双指针
     */
    @Test
    public void test_removeElementTwoPointersCoextensive() {
        int[] nums = {3,2,2,3};
        int val = 3;

        RemoveElement removeElement = new RemoveElement();
        int result = removeElement.removeElementTwoPointersCoextensive(nums, val);
        System.out.println(result);
        print(nums, result);
    }

    /**
     * 测试反向双指针
     */
    @Test
    public void test_removeElementTowPointersReverse1() {
        int[] nums = {0,1,2,2,3,0,4,2};
        int val = 2;

        RemoveElement removeElement = new RemoveElement();
        int result = removeElement.removeElementTowPointersReverse1(nums, val);
        System.out.println(result);
        print(nums, result);
    }


    /**
     * 测试反向双指针
     */
    @Test
    public void test_removeElementTowPointersReverse2() {
        int[] nums = {};
        int val = 2;

        RemoveElement removeElement = new RemoveElement();
        int result = removeElement.removeElementTowPointersReverse2(nums, val);
        System.out.println(result);
        print(nums, result);
    }

    public void print(int[] nums, int len) {
        System.out.print("[");
        for (int i = 0; i < len; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println("]");
    }
}


标签:27,val,nums,int,RemoveElement,result,LeetCode,left
From: https://www.cnblogs.com/dolphinmind/p/18335553

相关文章

  • LeetCode | 977 SquaresOfASortedArray
    https://github.com/dolphinmind/datastructure/tree/datastructure-array主类packagecom.github.dolphinmind.array.binarysearch;/***@authordolphinmind*@ClassNameSquaresOfASortedArray*@description977.有序数组的平方*分析:有移除元素{......
  • LeetCode | 704 BinarySearch
    https://github.com/dolphinmind/datastructure/tree/datastructure-array主类packagecom.github.dolphinmind.array.binarysearch;/***@authordolphinmind*@ClassNameBinarySearch*@description704二分法搜索*前提条件:有序数组,且无重复元素......
  • *算法训练(leetcode)第三十五天 | 121. 买卖股票的最佳时机、122. 买卖股票的最佳时机 I
    刷题记录*121.买卖股票的最佳时机贪心*动态规划122.买卖股票的最佳时机II贪心*动态规划*123.买卖股票的最佳时机III*121.买卖股票的最佳时机leetcode题目地址贪心找左侧最小值、右侧最大值(与最小值求差最大),求差即为最大利润。时间复杂度:......
  • 代码随想录训练第三十天|01背包理论基础、01背包、LeetCode416.分割等和子集
    文章目录01背包理论基础01背包二维dp数组01背包一维dp数组(滚动数组)416.分割等和子集思路01背包理论基础背包问题的理论基础重中之重是01背包,一定要理解透!leetcode上没有纯01背包的问题,都是01背包应用方面的题目,也就是需要转化为01背包问题。所以我先通过纯01背......
  • 代码随想录训练第三十一天|LeetCode1049.最后一块石头的重量II、LeetCode494.目标和、
    文章目录1049.最后一块石头的重量II思路一维数组二维数组494.目标和思路一维数组解法二维数组解法474.一和零思路1049.最后一块石头的重量II有一堆石头,用整数数组stones表示。其中stones[i]表示第i块石头的重量。每一回合,从中选出任意两块石头,然后将它们一......
  • 代码随想录训练第三十二天|完全背包理论基础、LeetCode518.零钱兑换II、LeetCode377.
    文章目录完全背包理论基础完全背包总结518.零钱兑换II思路一维数组二维数组377.组合总和Ⅳ思路卡码网70.爬楼梯(进阶版)思路完全背包理论基础完全背包有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i]。每件物品都有无......
  • 代码随想录训练第三十三天|LeetCode322. 零钱兑换、LeetCode279.完全平方数、LeetCode
    文章目录322.零钱兑换思路279.完全平方数思路139.单词拆分思路多重背包背包总结遍历顺序01背包完全背包总结322.零钱兑换给你一个整数数组coins,表示不同面额的硬币;以及一个整数amount,表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果......
  • LeetCode 279 完全平方数
    题目描述给你一个整数n,返回和为n的完全平方数的最少数量。完全平方数是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9和16都是完全平方数,而3和11不是。思路使用动态规划,对于一个数n,要将其拆成几个完全平方数的和,并且要求完全......
  • Leetcode每日一题 20240729 682.棒球比赛
    题目描述你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成,过去几回合的得分可能会影响以后几回合的得分。比赛开始时,记录是空白的。你会得到一个记录操作的字符串列表ops,其中ops[i]是你需要记录的第i项操作,ops遵循下述规则:整数x:表示本回合新获......
  • Leetcode每日一题 202040726 2740.找出分区值
    题目描述给你一个正整数数组nums。将nums分成两个数组:nums1和nums2,并满足下述条件:数组nums中的每个元素都属于数组nums1或数组nums2。两个数组都非空。分区值最小。分区值的计算方法是|max(nums1)-min(nums2)|。其中,max(nums1)表示数组nums1......