数组去重
剑指 Offer 03. 数组中重复的数字【简单】
找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：2 <= n <= 100000
1
2
3
4
5
6
7
8
9
10
11
12
13
class Offer03 {
public int findRepeatNumber(int[] nums) {
// 直接用set遍历查找
Set<Integer> hashSet = new HashSet<>();
for (int n : nums) {
if (hashSet.contains(n)) {
return n;
}
hashSet.add(n);
}
return 0;
}
}
26. 删除排序数组中的重复项【简单】
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下:
1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
对于数组相关的算法问题，有一个通用的技巧：要尽量避免在中间删除元素，那我就先想办法把这个元素换到最后去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0){
return 0;
}
// 快慢指针，让慢指针slow走左后面，快指针fast走在前面探路，
// 找到一个不重复的元素就告诉slow并让slow前进一步。
int slow = 0;
int fast = 1;
while(fast < nums.length){
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
fast++;
}
return slow + 1;
}
}
有序链表去重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public ListNode removeDuplicates(ListNode head) {
if(head == null){
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while(fast != null){
if(fast.val != slow.val){
// nums[slow] = nums[fast]
slow.next = fast;
// slow++
slow = slow.next;
}
// fast++
fast = fast.next;
}
// 断开与后面重复元素的连接
slow.next = null;
return head;
}
}
27. 移除元素【简单】
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。 注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int removeElement(int[] nums, int val) {
if (nums.length == 0){
return 0;
}
int slow = 0;
// fast从0开始
int fast = 0;
while(fast < nums.length){
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
316. 去除重复字母【困难】
给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1:
输入: “bcabc”
输出: “abc”
示例 2:
输入: “cbacdcbc”
输出: “acdb”
注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public String removeDuplicateLetters(String s) {
// 用栈
Stack<Character> stk = new Stack<>();
// 维护一个计数器记录字符串中字符的数量
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
}
// 记录是否在已经得到的字符串中
boolean[] inStack = new boolean[26];
for (char c : s.toCharArray()) {
// 每遍历过一个字符，都将对应的计数减一
count[c - 'a']--;
if (inStack[c - 'a']) continue;
while (!stk.isEmpty() && stk.peek() > c) {
// 若之后不存在栈顶元素了，则停止 pop
if (count[stk.peek() - 'a'] == 0) {
break;
}
// 若之后还有，则可以 pop
inStack[stk.pop() - 'a'] = false;
}
stk.push(c);
inStack[c - 'a'] = true;
}
StringBuilder sb = new StringBuilder();
while (!stk.empty()) {
sb.append(stk.pop());
}
return sb.reverse().toString();
}
}
1081. 不同字符的最小子序列【中等】
返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。
同上一题。
