一道数组去重的算法题把东哥整不会了

GitHub undefined undefined undefined

培养框架思维,真正爱上算法!关注公众号查看更新文章👆

相关推荐:

读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目:

316.去除重复字母(中等)

1081.不同字符的最小子序列(中等)


关于去重算法,应该没什么难度,往哈希集合里面塞不就行了么?

最多给你加点限制,问你怎么给有序数组原地去重,这个我们旧文 如何高效地给有序数组/链表去重

本文讲的问题应该是去重相关算法中难度最大的了,把这个问题搞懂,就再也不用怕数组去重问题了。

这是力扣第 316 题「去除重复字母」,题目如下:

这道题和第 1081 题「不同字符的最小子序列」的解法是完全相同的,你可以把这道题的解法代码直接粘过去把 1081 题也干掉。

题目的要求总结出来有三点:

要求一、要去重

要求二、去重字符串中的字符顺序不能打乱 s 中字符出现的相对顺序

要求三、在所有符合上一条要求的去重字符串中,字典序最小的作为最终结果。

上述三条要求中,要求三可能有点难理解,举个例子。

比如说输入字符串 s = "babc",去重且符合相对位置的字符串有两个,分别是 "bac""abc",但是我们的算法得返回 "abc",因为它的字典序更小。

按理说,如果我们想要有序的结果,那就得对原字符串排序对吧,但是排序后就不能保证符合 s 中字符出现顺序了,这似乎是矛盾的。

其实这里会借鉴前文 单调栈解题框架 中讲到的「单调栈」的思路,没看过也无妨,等会你就明白了。

_____________

本文只能在 labuladong 公众号查看,关注后可直接搜索本站内容:

Copyright © labuladong 2020 all right reserved,powered by Gitbook该文件修订时间: 2021-04-19 18:19:21

results matching ""

    No results matching ""