算法篇02、数组相关算法--哈希表、优先队列，金三银四Android高级工程师面试题整理_Android

你可以按任意顺序返回答案。

解法一暴力解法可以在一个两层嵌套的for循环中遍历数组，直到找到两个数相加等于target；因为是一个双层嵌套的for循环，所以时间复杂度是o(n^2)级别的；

//leetcode01 两数之和数组无序暴力解法时间复杂度o(n^2)
public int[] twosum3(int[] nums, int target) {
int[] res = new int[2];
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i+1; j < nums.length; j++) {
if (nums[j] + nums[i] == target){
res[0] = i;
res[1] = j;
}
}
}
return res;
}

解法二借助hashmap 我们可以借助hashmap保存数组中的元素值和索引，然后遍历数组，去hashmap中查找是否存在 target-遍历到的当前值，如果存在说明两个数的和为target，此时直接把hashmap中保存的索引和遍历到的当前值的索引返回即可；并且这个过程只需要遍历一遍数组即可，是不是非常巧妙~ 时间复杂度是o(n)级别的；

//leetcode01 两数之和数组无序借助hashmap记录索引，时间复杂度o(n)
public int[] twosum2(int[] nums, int target) {
int[] res = new int[2];
hashmap<integer,integer> hashmap = new hashmap<>();
for (int i = 0; i < nums.length; i++) {
if (hashmap.containskey(target - nums[i])){
res[0] = hashmap.get(target - nums[i]);
res[1] = i;
}
hashmap.put(nums[i],i);
}
return res;
}

7、leetcode804–唯一的摩尔斯密码

国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串，比如: “a” 对应 “.-”, “b” 对应 “-…”, “c” 对应 “-.-.”, 等等。

为了方便，所有26个英文字母对应摩尔斯密码表如下：

[“.-”,“-…”,“-.-.”,“-…”,“.”,“…-.”,“–.”,“…”,“…”,“.—”,“-.-”,“.-…”,“–”,“-.”,“—”,“.–.”,“–.-”,“.-.”,“…”,“-”,“…-”,“…-”,“.–”,“-…-”,“-.–”,“–…”]

给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，“cab” 可以写成 “-.-…–…”，(即 “-.-.” + “.-” + “-…” 字符串的结合)。我们将这样一个连接过程称作单词翻译。

返回我们可以获得所有词不同单词翻译的数量。

题解如下所示，把数组中的所有单词都翻译成莫尔斯密码，然后保存到hashset中，最后返回hashset的size即可，因为hashset可以自动去重；

//leetcode 804 唯一的摩尔斯密码
public int uniquemorserepresentations(string[] words) {
hashset set = new hashset<>();
for (string word : words) {
string morsecode = transformwordtomorsecode(word);
set.add(morsecode);
}
return set.size();
}

private string transformwordtomorsecode(string word) {
string[] morse = {“.-”,“-…”,“-.-.”,“-…”,“.”,“…-.”,“–.”,“…”,“…”,“.—”,“-.-”,“.-…”,“–”,“-.”,“—”,“.–.”,“–.-”,“.-.”,“…”,“-”,“…-”,“…-”,“.–”,“-…-”,“-.–”,“–…”};
char[] chars = word.tochararray();
stringbuilder builder = new stringbuilder();
for (int i = 0; i < chars.length; i++) {
builder.append(morse[chars[i] - ‘a’]);
}
return builder.tostring();
}

8、leetcode75–颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

题解如下所示，我们可以借助快速排序中三路快排的思想解决这个问题；当元素为0时放在左边，当元素为1时放在中间，当元素为2时放在右边，最后遍历完也就排完序了，时间复杂度是o(n)级别的；

//leetcode 75 颜色排序，借助三路快排思想
public void sortcolors(int[] nums) {
int l = 0;
int r = nums.length - 1;
int m = l -1;
int n = r + 1;
//for循环走完后 [l…m]表示0；(m…n)表示1；[n…r]表示2；
for (int i = 0; i < n; ) {
if (nums[i] == 0){
swap(nums,m+1,i);
m++;
i++;
}else if (nums[i] == 2){
swap(nums,n-1,i);
n–;
}else {
i++;
}
}
}

//交换nums数组中a、b位置的元素
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}

9、leetcode347–前k个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

题解如下所示，本题很好的结合了哈希表和优先队列；我们首先遍历一边数组，将元素及其出现的次数保存到hashmap中；然后新建一个优先队列，使用hashmap的value值相减作为比较器，这样就保证了数的频率越高，其优先级越低；最后遍历一遍hashmap，在优先队列中元素小于k时直接放入，否则就比较队列首的元素和遍历到的元素，如果遍历到的元素的频率比队列首的元素的频率还高，就把队列首元素出队，让遍历到的元素入队；因为队列首的元素始终是优先队列中频率最低的那个；

因为就遍历了两遍数组，所以时间复杂度是o(2n)，忽略常数，时间复杂度就是o(n)级别的；

//leetcode347 前k个高频元素
public int[] topkfrequent(int[] nums, int k) {
hashmap<integer,integer> hashmap = new hashmap<>();
for (int num : nums) {
hashmap.put(num, hashmap.getordefault(num, 0) + 1);
}
priorityqueue queue = new priorityqueue<>(new comparator() {
@override
public int compare(integer a, integer b) {
return hashmap.get(a) - hashmap.get(b);
}
});

for (integer key : hashmap.keyset()) {
if (queue.size() < k){
queue.add(key);
}else if (hashmap.get(key) > hashmap.get(queue.peek())) {
queue.remove();
queue.add(key);
}
}

int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = queue.remove();
}
return res;
}

10、leetcode454–四数之和为0的元组

给定四个包含整数的数组列表 a , b , c , d ,计算有多少个元组 (i, j, k, l) ，使得 a[i] + b[j] + c[k] + d[l] = 0。

为了使问题简单化，所有的 a, b, c, d 具有相同的长度 n，且 0 ≤ n ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

解法一暴力解法

直接使用四层嵌套for循环遍历数组，不过此种方式时间复杂度为o(n^4)级别的，性能太差；

//leetcode454 四数之和为0的元组
//暴力解法四重循环，时间复杂度o(n^4),爆炸，无法忍受
public int foursumcount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
for (int k = 0; k < nums3.length; k++) {
for (int l = 0; l < nums4.length; l++) {
if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) {
res ++;
}
}
}
}
}
return res;
}

解法二借助哈希表

首先使用两层嵌套for循环遍历前两个数组，将前两个数组所有和及其出现的次数保存到hashmap中；然后再使用一个双层嵌套的for循环遍历后两个数组，在hashmap中找这两个数组元素和的相反数即可，主要找到之后加的是hashmap的value值；

//借助hashmap，时间复杂度降低为o(n^2)
public int foursumcount2(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
//key代表nums1和nums2元素相加的和，value代表和的个数
hashmap<integer,integer> hashmap = new hashmap<>();
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
int sum = nums1[i] + nums2[j];
hashmap.put(sum,hashmap.getordefault(sum,0) + 1);
}
}
int res = 0;
for (int i = 0; i < nums3.length; i++) {
for (int j = 0; j < nums4.length; j++) {
int sum = nums3[i] + nums4[j];
if (hashmap.containskey(-sum)){
res+=hashmap.get(-sum);
}
}
}
return res;
}

11、leetcode704–有序数组的二分搜索

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

有序数组的二分搜索是比较经典的算法问题，因为数组是有序的，每次去数组中间查找，如果中间的数比target还要小，就去右边子数组查找；如果中间的数比target还要大，就去左边子数组查找；如果等于target，直接返回；这样每次查找后都减少一半的元素，时间复杂度是o(logn)级别的；

//leetcode 704 有序数组的二分搜索
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while (l <= r){
int mid = l + (r - l) / 2;
if (nums[mid] < target){
l = mid + 1;
}else if (nums[mid] > target){
r = mid - 1;
}else {
return mid;
}
}
return -1;
}