[LintCode/LeetCode] Remove Duplicates from Sorted

WalkerXu 发布于2019-08-14 15:32 / 2646人阅读

摘要：思路原数组长度为，则返回原数组长度不为，则至少有个元素。将所有不重复的数值赋给，而当和相等时，不做处理。最后返回的就是不同元素的个数，也是新数组的长度。只有在时，才对赋值。注意，每次初始化的时候要分两种情况，这就意味着从的时候开始遍历。

Remove Duplicates from Sorted Array I Problem

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

Example

Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Note

思路：原数组长度为0，则返回0；原数组长度不为0，则至少有index = 1个元素。循环整个数组，比较nums[i]和nums[i-1]。将所有不重复的数值赋给nums[index]，而当nums[i]和nums[i-1]相等时，不做处理。最后返回的index就是不同元素的个数，也是新数组的长度。

Solution

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int index = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) nums[index++] = nums[i];
        }
        return index;
    }
}

Remove Duplicates from Sorted Array II Problem

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Note

相同的思路，加入一个count变量，每次循环比较前后元素是否重复时，更新该元素出现的次数count。只有在count <= 2时，才对nums[index]赋值。
注意，每次初始化count的时候要分两种情况：i == 0 || nums[i] != nums[i-1]，这就意味着从i = 0的时候开始遍历。

Solution

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int index = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 || nums[i] != nums[i-1]) count = 1;
            else count++;
            if (count <= 2) {
                nums[index] = nums[i];
                index++;
            }
        }
        return index;
    }
}

云服务器 GPU云服务器 Duplicates Sorted remove sorted-array

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

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

[LintCode/LeetCode] Find Minimum in Rotated Sorted

摘要：排序数组中找最小值或最大值的题目，很明显可以使用二分法。因此，只判断终点和中点元素的大小关系即可。这里有一种情况是上述后三个，中点值和末位相等。此时，两边同时递归，并返回两边递归值的较小值。当首位和末位重合，说明已夹逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

cgh1999520 2019-08-14 15:22 评论0 收藏0
[LintCode/LeetCode] Search Insert Position

Problem Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume NO duplicates in the a...

cjie 2019-08-14 15:40 评论0 收藏0
[Leetcode] Remove Duplicates from Sorted Array 移除有

摘要：双指针法复杂度时间空间思路我们可以将不重复的序列存到数列前面，因为不重复序列的长度一定小于等于总序列，所以不用担心覆盖的问题。代码双指针法复杂度时间空间思路思路和上题一样，区别在于记录前两个遍历到的数字来帮助我们判断是否出现了第三遍。 Remove Duplicates from Sorted Array I Given a sorted array, remove the dupl...

kel 2019-08-14 12:30 评论0 收藏0
leetcode82. Remove Duplicates from Sorted List II

摘要：题目要求翻译将链表中重复的元素全部删除，返回新的头结点。相比于，这里将重复的元素全部删除。除此以外，我们还需要知道重复元素的前一个值和重复元素的最后一个值。如果存在重复值，则跳过重复值后，前节点不变，否则前节点跟随后节点同时向后移动。题目要求 Given a sorted linked list, delete all nodes that have duplicate number...

崔晓明 2019-08-15 10:36 评论0 收藏0
leetcode80. Remove Duplicates from Sorted Array II

摘要：思路与代码其实在这里我们仍然延续中的思路。在遇到非重复值以及非多余的重复值时，将数值移动到当前记录的下标上。保证该下标前的值均为满足题目条件的值。第一次我使用了来记录某个值出现的次数。题目要求 Follow up for Remove Duplicates: What if duplicates are allowed at most twice? For example, Giv...

CoderDock 2019-08-15 10:42 评论0 收藏0