442. 数组中重复的数据【中等题】【每日一题】
思路1：【暴力】
开辟一个长度为n的cnt数组用来统计每个数字出现的次数(数字和数组下标的对应关系为 下标 = 数字 - 1)，然后遍历cnt数组，当个数等于2时，将下标 + 1 之后添加进入 ans 列表中。
可能因为测试用例的原因，我这暴力法比题解的方法用时还快~
代码：
class Solution {
public List findDuplicates(int[] nums) {
List ans = new ArrayList<>();
int n = nums.length;
int[] cnt = new int[n];
for (int num : nums) {
cnt[num-1]++;
}
for (int i = 0; i < n; i++) {
if (cnt[i] == 2){
ans.add(i+1);
}
}
return ans;
}
}
思路2：【注解三叶-原地哈希】
遍历数组的元素，设其下标为 i ，值为 t，尝试将其挪到下标为 t-1 的位置，在挪动之前先进行判断，如果此时i就是 t - 1，或者 此时t小于 0 ，那么不需要对这个位置的元素进行处理，继续处理下一个位置的数组元素即可。
判断完毕之后开始对数组进行处理：
如果此时数组下标为t - 1位置的元素已经是t了，而此时 i 又不是 t -1 ，此时我们认为这个位置的元素一定是重复的，将其添加到ans列表中，并将当前这个i位置的元素修改为 -1 表示我们已经确认这个位置元素是重复的，以后不需要对这个位置元素进行判断；
如果此时数组下标为t - 1位置的元素不是 t ，那么我们就将 t-1 位置 和 此时的i位置 对应的值进行交换 ，由于交换之后未对新的i位置元素进行上述一系列判断，因此我们需要将i-1之后重新对i位置的元素进行上述判断。
代码：
class Solution {
public List findDuplicates(int[] nums) {
List ans = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n; i++) {//遍历nums数组
int t = nums[i];//取出当前位置元素 t = nums[i]
if (t < 0 || t - 1 == i){//如果 t 已经被判断为重复元素 或 t 已经被确认为不重复元素，则跳过本次循环继续遍历下一个位置的元素
continue;
}
//尝试将 当前数字 t 放在它该出现的位置 下标 t-1
if (nums[t-1] == t){//如果 nums[t-1] == t 说明数字 t 已经出现在 它该出现的位置 而此时又可以确定 当前下标 i 不等于 t-1 ，那么说明这个 t 必然是重复的
ans.add(t); // t 是重复的，将 t 添加到ans列表中
nums[i] = -1; //将此时 t 所在的位置 i 对应的 t 标记为 -1 ，表示这个位置的元素是重复的
}else {//如果 nums[t-1] != t 则将 下标为 t-1 位置的元素与 当前下标 i 位置的元素(即 t )交换位置，然后重新对下标 i 位置的元素进行判断
int temp = nums[t-1];
nums[t-1] = t;
nums[i] = temp;
i--;//重新对 i 位置元素进行判断
}
}
return ans;
}
}
剑指 Offer II 033. 变位词组【中等题】
思路：【哈希】
统计每个单词中每个字母出现的次数，将字母和对应的出现次数拼接成字符串作为hashmap的key，将此时的单词存入key对应的value列表，如此处理完所有的单词之后，将map中的value集合转为ArrayList列表返回即可。
代码：
class Solution {
public List> groupAnagrams(String[] strs) {
Map> map = new HashMap<>();
for (String str : strs) {
int[] cnt = new int[26];
for (char c : str.toCharArray()) {
cnt[c-'a']++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (cnt[i] != 0){
sb.append((char)(cnt[i]+'a')).append(i);
}
}
String key = sb.toString();
List value = map.getOrDefault(key,new ArrayList<>());
value.add(str);
map.put(key,value);
}
return new ArrayList<>(map.values());
}
}
