数组/链表高效去重(算法题
2022/1/8 22:05:01
本文主要是介绍数组/链表高效去重(算法题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
有序数组/链表去重
对于数组相关的算法题,有一个通用的技巧:要尽量避免在中间删除元素,那我就先想办法把这个元素换到最后去。这样的话,最终待删除的元素都拖在数组尾部,一个一个 pop 掉就行了,每次操作的时间复杂度也就降低到 O(1) 了。
按照上面的思路可以使用双指针的方法,我们让慢指针slow
走左后面,快指针fast
走在前面探路,找到一个不重复的元素就告诉slow
并让slow
前进一步。
这样当fast
指针遍历完整个数组nums
后,nums[0..slow]
就是不重复元素,之后的所有元素都是重复元素
字母去重
最后做一道算是去重算法题中难度最大的,把这题搞懂去重部分的算法题应该就没问题了。
LeetCode 316 字母去重
给你一个字符串
s
,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
题目要求总结有三:
-
去重
-
不能打算输入字符串s中的字符出现的相对顺序
-
在符合前面两条的情况下,选出字典序最小的作为最终结果。
思路
-
通过使用布尔数组inStack来做到栈stk中不存在重复元素
-
顺序遍历字符串
s
,通过「栈」这种顺序结构的 push/pop 操作记录结果字符串,保证了字符出现的顺序和s
中出现的顺序一致。 -
利用单调栈的思路以及使用计数器count来不断pop掉不符合最小字典序的字符。
class Solution { public String removeDuplicateLetters(String s) { //存放去重结果 Stack<Character> stk = new Stack<>(); int[] count = new int[256]; for(int i=0;i<s.length();i++){ count[s.charAt(i)]++; } boolean[] inStack = new boolean[256]; for(char c:s.toCharArray()){ count[c]--; if(inStack[c]) continue; while(!stk.isEmpty()&&stk.peek()>c){ if(count[stk.peek()]==0){ break; } inStack[stk.pop()] = false; } stk.push(c); inStack[c] = true; } StringBuilder sb = new StringBuilder(); while(!stk.isEmpty()){ sb.append(stk.pop()); } //由于栈是先进后出的,所以要反转一次才是最终结果 return sb.reverse().toString(); } }
这篇关于数组/链表高效去重(算法题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求