漏掉的筷子长度(只出现一次的数字)，Map的遍历

发表于 更新于 分类于 评论数：
本文字数： 3.1k 阅读时长 ≈ 4 分钟

昨天华为的一面题目，没想到竟然挂在了一个这么简单的题目上：

小明是个马大哈，某天他到超市买了若干双筷子（n < 20），筷子的长度不尽相同，他把全部筷子都放在购物袋里面拿回家，路上不小心漏了一根，请你用程序帮他找出是漏掉的筷子是多长的。

题目看了半天，搞不懂输入输出应该是什么，问面试官输入只是一个n吗，回答说对的，你可以自己给筷子编号（wtf ？？）， 硬着头皮用n新建了一个空数组，然后暴力循环了两遍找里面单个的值。做完后心里想，既然已经知道了数组中每个筷子的长度，那我不就已经知道是掉了拿一根了嘛（真是想太多。。）面试官看了后说我的时间 复杂度太大，可以考虑换个数据结构。然后我就想到了键值对的Map， 面试官说你照着这个思路写一下，继续做的时候又陷入了怎么初始化数据的怪圈。。。

总体来说面试体验很差，一是题目没有明确输入与输出应该是什么，最起码有个案例也行啊。二是我经验不足，思考不够全面，被一道题卡在输入和数据初始化上不知道是我的问题还是我的问题，哎不说了，解题！

今天一起实习的小伙伴告诉我说其实就是类似找重复或者不重复的数，异或就可以实现。上网找了一下题目，果然有明确的输入和输出(我哭了，有这两句话我早就写出来了。。。)：

输入： 剩下的筷子数组，如：1, 2, 3, 2, 1, 3, 2
返回值：漏掉的筷子长度，如上述输入返回：2（当输入的筷子数据异常时返回-1，如：找不到漏掉的筷子）

暴力法

也就是我在面试的时候答出来的，循环两遍查找有无重复的值，若有重复值，则跳出小循环，判断下一个数是否在后面的数里面有重复。方法过于笨拙，就不贴代码了吧。嵌套循环，时间复杂度为O(n2)

异或法

先说一下异或的主要性质，在去重和找重方面经常应用：

0 ^ a = a;
a ^ a = 0;
去重：把所有的

下面是我写的代码，迭代器一次循环，时间复杂度为O(n)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int find1(int[] chopsticks) {
	if(chopsticks.length >=39) return -1;
	int result = 0;
	for(int chopLen:chopsticks) {
		result ^= chopLen;
	}
	return result;
}

//测试
public static void main(String[] args) {
	int[] chopsticks = {1,2,2,3,1,3,4};
	System.out.println(find1(chopsticks));
}

输出结果为4

Map遍历法

考虑面试官提示的key-value存储形式，当时卡在了map初始化上，还得多加练习

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
/**
 * Map解法
 */
public static int find2(int[] chopsticks) {
	//Key为筷子长度，Value为个数
	Map<Integer, Integer> map = new HashMap<Integer, Integer>();//初始化map，昨天也在这里卡住了
	for(int i:chopsticks) {
		if(map.containsKey(i)) {
			map.put(i, map.get(i)+1);//有重复则数值+1
		} else {
			map.put(i, 1);
		}
	}
  //遍历map，重点掌握
	for(Integer i:map.keySet()) {
		if(map.get(i) == 1) {
			return i;
		}
	}
	 return -1;
}

//测试
public static void main(String[] args) {
	int[] chopsticks = {1,2,2,3,1,3,4};
	System.out.println(find1(chopsticks));
}

输出结果为4

遍历Map的几种方法

代码过程中发现忘记了怎么遍历map。。。赶紧复习一波
参考博客
https://www.cnblogs.com/bingyimeiling/p/10741761.html

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
public static void main(String[] args) {
	// 循环遍历Map的4中方法
	Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	map.put(1, 2);

	// 1. entrySet遍历，在键和值都需要时使用（最常用）
	for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
		System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
	}

	// 2. 通过keySet或values来实现遍历,性能略低于第一种方式
	// 遍历map中的键
	for (Integer key : map.keySet()) {
		System.out.println("key = " + key);
	}
	// 遍历map中的值
	for (Integer value : map.values()) {
		System.out.println("key = " + value);
	}

	// 3. 使用Iterator遍历
	Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
	while (it.hasNext()) {
		Map.Entry<Integer, Integer> entry = it.next();
		System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
	}

	// 4. java8 Lambda
	// java8提供了Lambda表达式支持，语法看起来更简洁，可以同时拿到key和value，
	// 不过，经测试，性能低于entrySet,所以更推荐用entrySet的方式
	map.forEach((key, value) -> {
		System.out.println(key + ":" + value);
	});
}

  • 如果只是获取key，或者value，推荐使用keySet或者values方式；

  • 如果同时需要key和value推荐使用entrySet；

  • 如果需要在遍历过程中删除元素推荐使用Iterator；

  • 如果需要在遍历过程中增加元素，可以新建一个临时map存放新增的元素，等遍历完毕，再把临时map放到原来的map中。

使用迭代器遍历ArrayList和HashMap

0%