[Leetcode] Remove Element 刪除數(shù)組元素

spacewander 發(fā)布于2019-08-14 12:37 / 639人閱讀

摘要：只有不等于給定數(shù)字的數(shù)，才會被拷貝到子數(shù)組的邊界上。代碼只拷貝非給定數(shù)字的元素交換法復(fù)雜度時間空間思路因為題目中并不要求相對順序保持一致，所以有進一步優(yōu)化的空間。

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.

雙指針法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

用一個指針記錄不含給定數(shù)字的數(shù)組邊界，另一個指針記錄當(dāng)前遍歷到的數(shù)組位置。只有不等于給定數(shù)字的數(shù)，才會被拷貝到子數(shù)組的邊界上。

代碼

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

交換法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

因為題目中并不要求相對順序保持一致，所以有進一步優(yōu)化的空間。我們遍歷數(shù)組時，每遇到一個目標(biāo)數(shù)，就和當(dāng)前數(shù)組結(jié)尾交換，并把數(shù)組大小減1，如果不是目標(biāo)數(shù)，則檢查下一個數(shù)字。這樣可以減少很多賦值操作。

代碼

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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64597.html

相關(guān)文章

LeetCode-Remove Element-從排序數(shù)組中刪除重復(fù)項

摘要：描述給定一個有序數(shù)組，你需要原地刪除其中的重復(fù)內(nèi)容，使每個元素只出現(xiàn)一次并返回新的長度。最后慢指針指向的元素及前面所有元素都是不重復(fù)的。描述：給定一個有序數(shù)組，你需要原地刪除其中的重復(fù)內(nèi)容，使每個元素只出現(xiàn)一次,并返回新的長度。不要另外定義一個數(shù)組，您必須通過用 O(1) 額外內(nèi)存原地修改輸入的數(shù)組來做到這一點。示例：給定數(shù)組: nums = [1,1,2], 你的函數(shù)應(yīng)該返回新...

dayday_up 2019-07-30 16:07 評論0 收藏0
Java中如何優(yōu)雅地刪除List中的元素

摘要：刪除元素后，立即跳出，則正常退出，但不能向后繼續(xù)循環(huán)了刪除后立馬終端循環(huán)，會正常跳出，但代價是不能繼續(xù)向后循環(huán)了使用迭代器使用迭代器可，正確無誤的刪除，代碼簡潔優(yōu)雅，推薦使用使用迭代器可，正確無誤的刪除注意這里時而不是在工作中的許多場景下，我們都會使用到List這個數(shù)據(jù)結(jié)構(gòu)，那么同樣的有很多場景下需要刪除List中的某一個元素或某幾個元素，那么我們該如何正確無誤地刪除List中的元素...

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

摘要：題目要求設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，使得能夠在的時間復(fù)雜度中插入數(shù)字，刪除數(shù)字，以及隨機獲取一個數(shù)字。因此，使用來查詢時不可避免的。如何實現(xiàn)的隨機查詢這個其實就是強調(diào)一點，我們需要維持原有的插入順序，從而保證各個元素等概率被隨機。題目要求 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

摘要：題目要求設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，支持能夠在的時間內(nèi)完成對數(shù)字的插入，刪除和獲取隨機數(shù)的操作，允許插入重復(fù)的數(shù)字，同時要求每個數(shù)字被隨機獲取的概率和該數(shù)字當(dāng)前在數(shù)據(jù)結(jié)構(gòu)中的個數(shù)成正比。網(wǎng)上有一些實現(xiàn)采用來解決，這是不合理的。此時的代碼如下題目要求 Design a data structure that supports all following operations in average...

h9911 2019-08-16 15:06 評論0 收藏0
?LeetCode 26：刪除排序數(shù)組中的重復(fù)項 Remove Duplicates from So

給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 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