算法题丨Remove Duplicates from Sorted Array

简介: 描述Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

描述

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 by modifying the input array in-place with O(1) extra memory.

示例

Given nums = [1,1,2],
    
Your function should return length = 2, with the first two elements of nums being 
1 and 2 respectively.
It doesn't matter what you leave beyond the new length.

算法分析

难度:低
分析:要求给定的排序后的数组,将其中重复的元素去除(是的每个元素只出现一次),并返回最终数组的长度。算法不要分配额外的数组空间。
思路:既然输入的数组已然排好序,我们可以定义i,j两个数组下标值,开始i初始为0,用来记录数组中有效元素下标,j从1开始,用来记录遍历数组的下标:
如果数组[j]==数组[i],表示有重复,重复元素个数i不用累计,遍历数组下一条;
如果数组[j]!=数组[i],表示没有重复,有效元素下标i自增+1,把数组[i]值用数组[j]替代,比较下一个元素;
依次遍历,直到数组[j]至最后一个元素,最终[0,i]范围内的数组元素,即为题目要求的结果。

代码示例(C#)

public int RemoveDuplicates(int[] nums)
{
    if (nums.Length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.Length; j++)
    {
        //不重复的话,有效索引+1,将当前元素值记录在索引对应的数组上
        if (nums[j] != nums[i])
        {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}                                           

复杂度

  • 时间复杂度O (n).
  • 空间复杂度O (1).

附录

img_8f0a90f3cbaa0e044fb8bf7b13c4317b.jpe

文章作者:原子蛋
文章出处:https://www.cnblogs.com/lizzie-xhu/
个人网站:https://www.lancel0t.cn/
个人博客:https://blog.lancel0t.cn/
微信公众号:原子蛋Live+
扫一扫左侧的二维码(或者长按识别二维码),关注本人微信公共号,获取更多资源。
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

目录
相关文章
|
4月前
|
JavaScript 算法 前端开发
JS算法必备之Array常用操作方法
这篇文章详细介绍了JavaScript中数组的创建、检测、转换、排序、操作方法以及迭代方法等,提供了数组操作的全面指南。
JS算法必备之Array常用操作方法
Leetcode Find Minimum in Rotated Sorted Array 题解
对一个有序数组翻转, 就是随机取前K个数,移动到数组的后面,然后让你找出最小的那个数,注意,K有可能是0,也就是没有翻转。
50 0
Search in Rotated Sorted Array - 循环有序数组查找问题
Search in Rotated Sorted Array - 循环有序数组查找问题
72 0
|
算法
LeetCode Find Minimum in Rotated Sorted Array II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 注意数组中可能存在重复的元素。
87 0
LeetCode Find Minimum in Rotated Sorted Array II
LeetCode 153. Find Minimum in Rotated Sorted Array
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 你可以假设数组中不存在重复元素。
107 0
LeetCode 153. Find Minimum in Rotated Sorted Array
LeetCode 108. Convert Sorted Array to BST
给定一个数组,其中元素按升序排序,将其转换为高度平衡的BST。 对于这个问题,高度平衡的二叉树被定义为:二叉树中每个节点的两个子树的深度从不相差超过1。
78 0
LeetCode 108. Convert Sorted Array to BST
LeetCode 88. Merge Sorted Array
题意是给定了两个排好序的数组,让把这两个数组合并,不要使用额外的空间,把第二个数组放到第一个数组之中.
85 0
LeetCode 88. Merge Sorted Array
|
索引
LeetCode 81. Search in Rotated Sorted Array II
假设按升序排序的数组在事先未知的某个枢轴处旋转。 (例如, [0,0,1,2,2,5,6] 可能变成 [2,5,6,0,0,1,2]). 给定一个要搜索的目标值T, 如果该目标值能在数组中找到则返回true,否则返回false。
92 0
LeetCode 81. Search in Rotated Sorted Array II
LeetCode 80 Remove Duplicates from Sorted Array II
给定排序的数组nums,就地删除重复项,使重复项最多出现两次并返回新的长度. 不要为另一个数组分配额外的空间,必须通过使用O(1)复杂度的额外空间来修改输入数组,从而实现此目的.
70 0
LeetCode 80 Remove Duplicates from Sorted Array II
|
存储 算法 Python
Python数据结构与算法(7)---数组array
Python数据结构与算法(7)---数组array
125 0
Python数据结构与算法(7)---数组array