leetcode26 remove duplicate

syoya 发布于2019-08-14 17:52 / 2752人阅读

摘要：题目要求输入一个数组和一个值，删除数组中等于该值得元素。但是在数组的容量非常大且数组中该数字出现频率不高的情况下，使用两个指针可以明显减少程序遍历数组的时间。

题目要求：输入一个数组和一个值，删除数组中等于该值得元素。不允许分配新的内存空间（即不允许创建新的数组），允许数组中的元素的顺序发生变化，只要该数组在返回长度前的值正确
例如：输入nums = [3,2,2,3], val = 3，程序返回2，且nums数组的前两个值均为2

使用一个指针
时间复杂度O(n), 空间复杂度O(1)

/**
 * @author rale
 * 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 in place with constant memory.
 * The order of elements can be changed. It doesn"t matter what you leave beyond the new length.
 * Example:
 * Given input array nums = [3,2,2,3], val = 3
 * Your function should return length = 2, with the first two elements of nums being 2.
 */
public class RemoveElement {
    
    public int removeElement(int[] nums, int val) {
        int index = 0;
        for(int i = 0 ; i
使用两个指针
时间复杂度O(n) 空间复杂度O(1)
/**
 * @author rale
 * 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 in place with constant memory.
 * The order of elements can be changed. It doesn"t matter what you leave beyond the new length.
 * Example:
 * Given input array nums = [3,2,2,3], val = 3
 * Your function should return length = 2, with the first two elements of nums being 2.
 */
public class RemoveElement {
    
    public int removeElement(int[] nums, int val) {
        if(nums==null || nums.length==0){
            return 0;
        }
        int leftPointer = 0;
        int rightPointer = nums.length-1;
        while(leftPointer<=rightPointer){
            if(nums[rightPointer]==val){
                rightPointer--;
                continue;
            }
            if(nums[leftPointer]==val){
                nums[leftPointer] = nums[rightPointer];
                rightPointer--;
            }
            leftPointer++;
        }
        return rightPointer+1;
    }
}
leetcode的测试用例得出的性能分析发现，使用一个指针比使用两个指针的速度更快。但是在数组的容量非常大且数组中该数字出现频率不高的情况下，使用两个指针可以明显减少程序遍历数组的时间。
leetcode上也给出了参考答案

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

专线服务云服务器 Duplicates duplicated DUPLICATE Leetcod

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

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

leetcode 26 Remove Duplicates from Sorted Array

摘要：题目比较简单，就是找出数组不重复的数字，返回不重复的数字个数。无需删除重复数字，只需要保证数组的前位为不重复的个数字即可代码如下 Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not all...

alaege 2019-08-14 18:07 评论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
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...

cnTomato 2019-07-31 11:28 评论0 收藏0
leetcode刷题记录-【26 Remove Duplicates from Sorted Ar

摘要：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用额外空间的条件下完成。声明两个指针，为快指针，为慢指针如果遇到相同的数，那么就跳过，。给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组...

heartFollower 2019-08-19 11:46 评论0 收藏0
[LintCode/LeetCode] Remove Duplicate Letters

Problem Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical...

wanghui 2019-08-15 18:01 评论0 收藏0