leetcode26 remove duplicate

syoya 發布于2019-08-14 17:52 / 2893人閱讀

摘要：題目要求輸入一個數組和一個值，刪除數組中等于該值得元素。但是在數組的容量非常大且數組中該數字出現頻率不高的情況下，使用兩個指針可以明顯減少程序遍歷數組的時間。

題目要求：輸入一個數組和一個值，刪除數組中等于該值得元素。不允許分配新的內存空間（即不允許創建新的數組），允許數組中的元素的順序發生變化，只要該數組在返回長度前的值正確
例如：輸入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上也給出了參考答案

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Duplicates duplicated DUPLICATE Leetcod

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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