[算法题] Remove Duplicates from Sorted Array
2024-08-28 20:39:54
题目内容
本题来源于LeetCode
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.
For example,
Given input array 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.
题目思路
本题难度等级: easy
本题要求的是原地进行处理,而且不能够申请新的空间。本题采用的方法是数组当中非常常见的处理方法:快慢指针。
方法是:分别设立两个指针index,i。初始情况下,index和i都指向数组的第一个元素。i为快指针,index为慢指针。 i从第一个元素一直扫描到最后一个元素。index是慢指针,仅当nums[i]!=nums[index]的时候,index才会自增1。当扫描结束的时候,index指向的是不重复数组的最后一个元素,其长度为index+1
Python代码
class Solution:
# @param a list of integers
# @return an integer
def removeDuplicates(self, A):
if not A:
return 0
index= 0
for i in range( len(A)):
if A[i] != A[index]:
index+= 1
A[index] = A[i]
return index+ 1
最新文章
- ionic ios 发布设置 header-bar高度无效
- [Android] 深入浅出Android App耗电量统计
- GAT2.0使用文档(组合接口测试)
- redis 安装及相关问题解决
- 第六章 - 图像变换 - 图像拉伸、收缩、扭曲、旋转[2] - 透视变换(cvWarpPerspective)
- FineReader Mac如何设置参数让导出为DOCX/RTF/ODT格式
- checkbox与文字的间距
- windows下的python扩展包下载地址
- HDOJ2024C语言合法标识符
- leetcode—triangle
- Scala闭包
- 统计功能和子对象的大小信息查询Bug
- TFS 如何恢复到指定版本
- poj 3177
- JQuery 拖动层
- String VS Cstring(字符串)
- ionic2 使用 cordova 打包成安卓apk
- mysql对binlog的处理
- MySql 中文乱码解决办法
- Scala编程快速入门系列(一)