[LintCode/LeetCode] Remove Element [Two Pointers]

EdwardUp 發布于2019-08-14 15:21 / 991人閱讀

摘要：雙指針頭指針等于指定元素的時候，用尾指針的值替換的值否則頭指針繼續向后走。最后返回，就是所有非元素的數量。

Problem

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

The order of elements can be changed, and the elements after the new length don"t matter.

Example

Given an array [0,4,4,0,0,2,4,4], value=4

return 4 and front four elements of the array is [0,0,0,2]

Note

雙指針I：頭指針i等于指定元素elem的時候，用尾指針j的值替換i的值（A[i] = A[--j]）；否則頭指針i繼續向后走。
雙指針II：i和j都作為頭指針，當i的值不是指定元素elem的時候，將A[i]復制到j的位置；否則i繼續向后走。最后返回j，就是所有非elem元素的數量。

Solution

1. 雙指針I

public class Solution {
    public int removeElement(int[] A, int elem) {
        int i = 0, j = A.length;
        while (i < j) {
            if (A[i] == elem) {
                A[i] = A[--j];
            }
            else i++;
        }
        return j;
    }
}

2. 雙指針II

public class Solution {
    public int removeElement(int[] A, int elem) {
        int i = 0, j = 0;
        while (i < A.length) {
            if (A[i] != elem) {
                A[j++] = A[i];
            }
            i++;
        }
        return j;
    }
}

GPU云服務器云服務器 two-pointers Pointers Element remove

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65664.html

[LintCode/LeetCode] Intersection of Two Arrays I &

摘要：先想到的是，其實也可以，只是需要在遍歷的時候，添加到數組中的數要掉，略微麻煩了一點。在里跑的時候，也要快一點。另一種類似做法的就快的多了。如果是找出所有包括重復的截距呢 Problem Given two arrays, write a function to compute their intersection. Notice Each element in the result m...

enda 2019-08-14 14:03 評論0 收藏0
[LintCode/LeetCode] Subsets & Subsets II

Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

tracy 2019-08-14 14:26 評論0 收藏0
[LintCode/LeetCode] Trapping Rain Water [棧和雙指針]

摘要：一種是利用去找同一層的兩個邊，不斷累加寄存。雙指針法的思想先找到左右兩邊的第一個峰值作為參照位，然后分別向后向前每一步增加該位與參照位在這一位的差值，加入，直到下一個峰值，再更新為新的參照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

bluesky 2019-08-14 15:19 評論0 收藏0
[LintCode/LeetCode] Remove Duplicates from Sorted

摘要：思路原數組長度為，則返回原數組長度不為，則至少有個元素。將所有不重復的數值賦給，而當和相等時，不做處理。最后返回的就是不同元素的個數，也是新數組的長度。只有在時，才對賦值。注意，每次初始化的時候要分兩種情況，這就意味著從的時候開始遍歷。 Remove Duplicates from Sorted Array I Problem Given a sorted array, remove ...

WalkerXu 2019-08-14 15:32 評論0 收藏0
[LintCode/LeetCode] Contains Duplicate II

Problem Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at ...

894974231 2019-08-19 10:48 評論0 收藏0