[LintCode/LeetCode] Remove Element [Two Pointers]

EdwardUp 发布于2019-08-14 15:21 / 842人阅读

摘要：双指针头指针等于指定元素的时候，用尾指针的值替换的值否则头指针继续向后走。最后返回，就是所有非元素的数量。

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

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

转载请注明本文地址：https://www.ucloud.cn/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