乐趣区

关于算法:每日算法之数组二

jiezi

题目

给你一个 升序排列 的数组 nums，请你 原地 删除反复呈现的元素，使每个元素 只呈现一次，返回删除后数组的新长度。元素的 绝对程序 应该放弃 统一。

因为在某些语言中不能扭转数组的长度，所以必须将后果放在数组 nums 的第一局部。更标准地说，如果在删除反复项之后有 k 个元素，那么 nums 的前 k 个元素应该保留最终后果。

将最终后果插入 nums 的前 k 个地位后返回 k。

不要应用额定的空间，你必须在 原地 批改输出数组 并在应用 O(1) 额定空间的条件下实现。

示例 

 输出：nums = [1,1,2]
输入：2, nums = [1,2,_]
解释：函数应该返回新的长度 2，并且原数组 nums 的前两个元素被批改为 1, 2。不须要思考数组中超出新长度前面的元素。
 输出：nums = [0,0,1,1,1,2,2,3,3,4]
输入：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5，并且原数组 nums 的前五个元素被批改为 0, 1, 2, 3, 4。不须要思考数组中超出新长度前面的元素。

题目解析

这也是一道数组简略题，会应用一种常见的解题办法 – 快慢指针，次要用于一些前后对照的场景，在此题中须要前后对照看是否反复。开始之前首先须要思考一些边界状况如数组的长度为 0，此时新数组也为 0。当数组数组的长度大于 0 时，数组中至多蕴含一个元素，在删除反复元素之后也至多剩下一个元素，因而 nums[0] 保持原状即可，从下标 1 开始删除反复元素。定义两个指针 fast 和 slow 别离为快指针和慢指针，快指针示意遍历数组达到的下标地位，慢指针示意下一个不同元素要填入的下标地位，初始时两个指针都指向下标 1。假如数组 \textit{nums}nums 的长度为 nn。将快指针 \textit{fast}fast 顺次遍历从 11 到 n-1n−1 的每个地位，对于每个地位，如 nums[fast]
!=nums[fast−1]，阐明 nums[fast] 和之前的元素都不同，因而将 nums[fast] 的值复制到 nums[slow]，而后将 slow 的值加 1，遍历完结之后，从 nums[0] 到 nums[slow−1] 的每个元素都不雷同且蕴含原数组中的每个不同的元素，因而新的长度即为 slow，返回 slow 即可。

JAVA

class Solution {public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;

        int slow = 1, fast = 1;
        while (fast < n) {if (nums[fast] != nums[fast-1]) {nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}

Python3

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        slow = fast = 1
        while fast < len(nums):
            if nums[fast] != nums[fast-1]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

C++

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {int n = nums.size();
        if (n == 0) return 0;
        
        int slow = 1, fast = 1;
        while (fast < n) {if (nums[fast] != nums[fast-1]) {nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};

最初

有趣味能够关注公众号 QStack，回复“Android”即可取得收费的学习材料。

退出移动版