当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.027.Remove Element

LeetCode.027.Remove Element


题目描述

Given an array and a value, remove all instances of that value in-place and return the new length.

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

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:

Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.

解题过程

原地移除数组中指定元素并返回新数组。题目要求不得额外申请新数组,但超过新数组长度的元素不做要求。
看到这道题就想到使用交换双指针来做,一个指针low从前往后扫描,另一个指针high从后往前扫描,遇到要删除的元素就换到后面去,保证
low之前都是要保留的元素,high之后都是要删除的元素,写起来改了好几遍才改对:

package _027_RemoveElement;

class Solution {
    public int removeElement(int[] nums, int val) {
        int i=0,j=nums.length-1;
        while(i<=j){
            if(val == nums[j])
                j--;
            if(val != nums[i])
                i++;
            if(i<j && val == nums[i] && val != nums[j]){
                nums[i] ^= nums[j];
                nums[j] ^= nums[i];
                nums[i++] ^= nums[j--];
            }
        }
        return j+1;
    }
}

public class RemoveElement {
    public static void main(String[] args){
        int[] input = {};
        Solution solution = new Solution();
        System.out.println(solution.removeElement(input, 3));
        for(int a:input)
            System.out.print(a);
    }
}

我的方法速度还可以,打败了43%的submission,但比较麻烦,需要单独考虑的情况比较多。

这道题的Solution中介绍的两种方法非常好,简单且容易理解:

快慢双指针覆盖法

慢指针slow和快指针fast都从前往后扫描,快指针遇到要保留的元素就赋值给慢指针、遇到要删除的元素就跳过,保证慢指针slow之前都是要保留的元素

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

前后双指针交换法

快慢双指针覆盖法的缺点是所有需要保留的元素都要经过一次赋值,遇到删除元素很稀疏的情况效率很低,因为做了大量不必要的赋值操作,所以有了改进版的前后双指针交换法:前指针low从前往后扫描,遇到要删除的元素将其和后指针high交换(实际操作中不需要真正的交换,只需将后指针元素值赋值给前指针,因为超过新数组长度的元素不做要求),由于换过来的后指针元素也可能是要删除的元素,所以发生交换时前指针不后移,下次循环时再判断一遍

public int removeElement(int[] nums, int val) {
    int i = 0; //前指针
    int n = nums.length; //后指针
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            // reduce array size by one
            n--;
        } else {
            i++;
        }
    }
    return n;
}

GitHub代码


上一篇 LeetCode.026.Remove Duplicates from Sorted Array

下一篇 Hexo博客(21)创建博客概览插件

阅读
731
阅读预计3分钟
创建日期 2018-02-21
修改日期 2018-02-25
类别
百度推荐