[Leetcode] Remove Element 删除数组元素

spacewander 发布于2019-08-14 12:37 / 516人阅读

摘要：只有不等于给定数字的数，才会被拷贝到子数组的边界上。代码只拷贝非给定数字的元素交换法复杂度时间空间思路因为题目中并不要求相对顺序保持一致，所以有进一步优化的空间。

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn"t matter what you leave beyond the new length.

双指针法 复杂度

时间 O(N) 空间 O(1)

思路

用一个指针记录不含给定数字的数组边界，另一个指针记录当前遍历到的数组位置。只有不等于给定数字的数，才会被拷贝到子数组的边界上。

代码

public class Solution {
    public int removeElement(int[] nums, int val) {
        int pos = 0;
        for(int i = 0; i < nums.length; i++){
            // 只拷贝非给定数字的元素
            if(nums[i] != val){
                nums[pos] = nums[i];
                pos++;
            }
        }
        return pos;
    }
}

交换法 复杂度

时间 O(N) 空间 O(1)

思路

因为题目中并不要求相对顺序保持一致，所以有进一步优化的空间。我们遍历数组时，每遇到一个目标数，就和当前数组结尾交换，并把数组大小减1，如果不是目标数，则检查下一个数字。这样可以减少很多赋值操作。

代码

public class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length, i = 0;
        while(i < size){
            if(nums[i] == val){
                swap(nums, i, size - 1);
                size--;
            } else {
                i++;
            }
        }
        return size;
    }
    
    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64597.html

LeetCode-Remove Element-从排序数组中删除重复项

摘要：描述给定一个有序数组，你需要原地删除其中的重复内容，使每个元素只出现一次并返回新的长度。最后慢指针指向的元素及前面所有元素都是不重复的。描述：给定一个有序数组，你需要原地删除其中的重复内容，使每个元素只出现一次,并返回新的长度。不要另外定义一个数组，您必须通过用 O(1) 额外内存原地修改输入的数组来做到这一点。示例：给定数组: nums = [1,1,2], 你的函数应该返回新...

dayday_up 2019-07-30 16:07 评论0 收藏0
Java中如何优雅地删除List中的元素

摘要：删除元素后，立即跳出，则正常退出，但不能向后继续循环了删除后立马终端循环，会正常跳出，但代价是不能继续向后循环了使用迭代器使用迭代器可，正确无误的删除，代码简洁优雅，推荐使用使用迭代器可，正确无误的删除注意这里时而不是在工作中的许多场景下，我们都会使用到List这个数据结构，那么同样的有很多场景下需要删除List中的某一个元素或某几个元素，那么我们该如何正确无误地删除List中的元素...

kelvinlee 2019-08-16 13:53 评论0 收藏0
leetcode380. Insert Delete GetRandom O(1)

摘要：题目要求设计一个数据结构，使得能够在的时间复杂度中插入数字，删除数字，以及随机获取一个数字。因此，使用来查询时不可避免的。如何实现的随机查询这个其实就是强调一点，我们需要维持原有的插入顺序，从而保证各个元素等概率被随机。题目要求 Design a data structure that supports all following operations in average O(1)...

phoenixsky 2019-08-16 15:06 评论0 收藏0
leetcode381. Insert Delete GetRandom O(1) - Duplic

摘要：题目要求设计一个数据结构，支持能够在的时间内完成对数字的插入，删除和获取随机数的操作，允许插入重复的数字，同时要求每个数字被随机获取的概率和该数字当前在数据结构中的个数成正比。网上有一些实现采用来解决，这是不合理的。此时的代码如下题目要求 Design a data structure that supports all following operations in average...

h9911 2019-08-16 15:06 评论0 收藏0
LeetCode 26：删除排序数组中的重复项 Remove Duplicates from So

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and re...

Alan 2019-08-16 18:35 评论0 收藏0