Java描述 LeetCode，27. Remove Element 移出元素

63 阅读 0 评论 42 点赞

我是靠谱客的博主平淡皮皮虾，最近开发中收集的这篇文章主要介绍Java描述 LeetCode，27. Remove Element 移出元素，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞与关注是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。

1-1：题目描述

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目理解：
☘️看上去看复杂哈，其实就是在一个数组中删除元素，但是你未必真删，只要将剩余元素集中在数组的前面并且用一个值来代表多少位数组是有效的就可以了。这样，你就可以看懂example中的例子了。

1-2：前后指针解法

☘️当我看到这道题目的时候，最先想到的就是快排里面的前后指针，核心思想就是，从前向后找到=val的值，和从后向前找到!=val的值，然后把这两个值交换，不就完事了~但是要明白一点，这种做法必须要有轴值才行啊，这里的val可以当轴值。下一道题目里面，我们就不能用这种方法。

/**
 * 前后指针解法
 *
 * @param nums
 * @param val
 * @return
 */
public int removeElement(int[] nums, int val) {
    int n = nums.length;
    int first = 0;
    int last = n - 1;
    int newLength = n;
    while (first <= last) {
        // 从后向前,
        while (first <= last && nums[last] == val) {
            newLength--;
            last--;
        }
        while (first <= last && nums[first] != val) {
            first++;
        }
        if (first < last) {
            int temp = nums[first];
            nums[first] = nums[last];
            nums[last] = temp;
        }
    }

//        return first;
    return newLength;
}

时间复杂度O(N)
空间复杂度O(1)

1-3：快慢指针

☘️核心思想：慢指针指向需要存储的节点，快指针去遍历数组中所有的值。当快指针遇到val的时候，继续向前，遇到非val的时候，将值存进nums[slow]中去。slow永远指向待存的空间中，这样作为返回值，正好代表数组的有效长度。

/**
 * 快慢指针解法
 *
 * @param nums
 * @param val
 * @return
 */
public int removeElement2(int[] nums, int val) {
    int n = nums.length;
    int slow = 0;
    for (int fast = 0; fast < n; fast++) {
        if (nums[fast] != val) {
            // 没存入一个数之后slow++，所以slow代表数组中下一个将要存放值的位置
            // 也可以用作是代表数组的长度。
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

时间复杂度O(N)
空间复杂度O(1)

1-3：快慢指针优化-前后指针

如果要移除的元素恰好在数组的开头，例如序列 [1,2,3,4,5]，当 val 为 1 时，我们需要把每一个元素都左移一位。注意到题目中说：「元素的顺序可以改变」。实际上我们可以直接将最后一个元素 5 移动到序列开头，取代元素 1，得到序列 [5,2,3,4]，同样满足题目要求。这个优化在序列中 val 元素的数量较少时非常有效。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-element/solution/yi-chu-yuan-su-by-leetcode-solution-svxi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

等于说，移动数组的这个过程在有些情况可以省去的，确实，是个优化点。代码如下：

public int removeElement3(int[] nums, int val) {
    int n = nums.length;
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        if (nums[left] == val) {
            nums[left] = nums[right];
            right--;
        } else {
            left++;
        }
    }
    return left;
}