【JAVA】力扣-26-删除有序数组中的重复项
2023-09-27 14:26:46 时间
一、问题
力扣题目链接:删除有序数组中的重复项
提示:
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列
二、解题思路
由于数组已经排序,所以重复的元素一定连在一起,但如果毎找到一个重复元素就立即原地删除它,由于数组中删除元素涉及数据搬移,整个时间复杂度是会达到 O(N^2)。
高效解决这道题就要用到快慢指针技巧:
我们让慢指针 slow 走在后面,快指针 fast 走在前面探路,找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。
这样,就保证了 nums[0…slow] 都是无重复的元素,当 fast 指针遍历完整个数组 nums 后,nums[0…slow] 就是整个数组去重之后的结果。
三、解题代码
int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度 + 1
return slow + 1;
}
相关文章
- java数组反射实现动态的判断一个对象是否是数组并且对数组进行拆包输出
- java中同步嵌套引起的死锁事例代码
- Effective Java 第三版——55. 明智而审慎地返回Optional
- java数组三种初始化方式
- 细述 Java垃圾回收机制→Types of Java Garbage Collectors
- freemarker遍历java.util.Properties
- Java 只有值传递!为什么?
- java将字符串分割为数组,万分膜拜!
- 我是如何理解Java抽象类和接口的
- java equals
- Java中的锁-悲观锁、乐观锁,公平锁、非公平锁,互斥锁、读写锁
- 传智播客Java 二维数组
- Java Arrays:专为数组而生的工具类
- JAVA中堆栈和内存分配原理
- JAVA String对象和字符串常量的关系解析
- Difference Between Method Overloading and Method Overriding in Java
- 阻止Java反编译蛋疼方法
- Java内部类持有外部类的引用详细分析与解决方案
- Java 对微信小程序包wxapkg解包(反编译)解码方法及示例代码
- 动画基础(一) 四种基本动画(xml和java编写)
- java递归删除目录下所有内容
- 【存在重复元素(217-java)】