数据结构课程笔记1-水王问题

题目

给定一个数组，若数组里存在某个数字，其数量超过数组长度的一半以上，则称该数为水王数字。
例如数组[3,2,1,2,3,3,4,3,3],数字3为水王数字。若不存在水王数字，则返回-1；

要求时间复杂度：o(n)，空间复杂度:o(1)

解法一 (空间复杂度不满足要求)

思路：遍历数组，使用一个map来记录数字出现次数，找出出现次数大于数组长度1/2的数字。

public static int waterKing(int[] nums) {int result = -1;if (nums != null || nums.length != 0) {Map<Integer, Integer> map = new HashMap<>();for (int key : nums) {int count = map.getOrDefault(key, 0) + 1;map.put(key, count);if (count > nums.length / 2) {result = key;break;}}}return result;}

解法二 (满足时间与空间复杂度要求)

思路：遍历数组，若两个数不同，则同时删除，若相同，则保留，继续遍历。到最后，由于水王数字超过数组长度的1/2，若存在，一定可以留下。

代码思路：使用两个变量，一个为候选，一个为血量。血量记录候选出现的次数，当血量为0时，说明此时还没有真正的候选，可以将当前数字设置为候选，血量为1，继续遍历。若血量不为0，说明有候选，将候选数字与当前数字做对比，若相等，则候选血量加1，若不相等，则候选血量减少1。遍历完之后，若血量大于0，说明候选有可能真的为血王数字。再次遍历一遍数字，看是否候选数字次数大于数组长度的1/2。

代码：

public static int waterKing(int[] nums) {int candidate = 0;int restHP = 0;if (Objects.requireNonNull(nums).length > 0) {for (int key : nums) {if (restHP == 0) {candidate = key;restHP++;} else if (key == candidate) {restHP++;} else {restHP--;}}if (restHP != 0) {restHP = 0;for (int key : nums) {if (key == candidate) {restHP++;}}}}return restHP > nums.length / 2 ? candidate : -1;}

总结

以上是生活随笔为你收集整理的数据结构课程笔记1-水王问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。