分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign; import java.util.Arrays; /* * 在某一论坛坊间风闻有一“水王”发帖数目超过了帖子总数的一半。你能快速找出这个传说中的水王吗 * * ---------------- * * 摩尔投票法 * 核心思想“正负抵消”。 * * 思路 * 1.我们在遍历数组时维护两个变量candidate候选人和 times计数。 * 2.初始时candidate 为-1times 为 0。 * 3.遍历每一个 ID * 如果 times 为 0说明当前没有候选人或者之前的候选人都被抵消完了。我们将当前的 ID 设为新 * 的 candidate并将 times 设为 1。 * 如果当前的 ID 等于 candidate说明是“自己人”times 加 1。 * 如果当前的 ID 不等于 candidate说明是“敌人”times 减 1即消耗一张票抵消掉一个水王的 * 帖子。 * 4.为什么这样行得通 * 因为水王的帖子数 总数的一半。 * 即使我们将所有非水王的帖子都用来和水王的帖子进行“一对一”的消耗抵消最后剩下的肯定还是水王 * 的帖子。 * 这就像混战水王的人马最多即使每场战斗都和一个敌人同归于尽最后站在战场上的依然是水王的人。 */ public class FindWaterKing { private static int find(int[] id) { int candidate -1; int i, times; for (i 0, times 0; i id.length; i) { if (times 0) { candidate id[i]; times 1; } else { if (id[i] candidate) { times; } else { times--; } } } return candidate; } /* * 继上次水王找到之后论坛江湖又过了一段时间现又涌现出三个发帖很多的ID * 他们的发帖数目都超过了帖子总数目N的1/4。怎么从发贴的ID中快速找出他们的ID * * ---------------- * * 解题思路摩尔投票法的扩展 * 既然是 3 个水王我们就需要维护 3 个候选人和 3 个计数器。 * * 算法流程 * 1.建立三个候选人变量 candidate[0], candidate[1], candidate[2] 和对应的计数 times[0], * times[1], times[2]。 * 2.遍历数组 * 如果某个计数为 0则替换该候选人为当前 ID计数设为 1。 * 如果当前 ID 等于某个候选人对应的计数加 1。 * 如果当前 ID 不等于任何候选人且所有计数都不为 0则三个计数同时减 1相当于三个水王每人派出 * 一个兵力去抵消一个非水王的帖子。 * 3.最后剩下的三个候选人即为可能的解因为题目保证存在所以直接返回即可如果不保证存在还需要最 * 后遍历一遍验证这三个人的票数是否真的超过 1/4。 */ private static int[] find3(int[] id) { int[] candidate {-1, -1, -1}; int[] times {0, 0, 0}; int i; for (i 0; i id.length; i) { if (times[0] 0) { candidate[0] id[i]; times[0] 1; } else if (times[1] 0) { candidate[1] id[i]; times[1] 1; } else if (times[2] 0) { candidate[2] id[i]; times[2] 1; } else if (id[i] candidate[0]) { times[0]; } else if (id[i] candidate[1]) { times[1]; } else if (id[i] candidate[2]) { times[2]; } else { times[0]--; times[1]--; times[2]--; } } return candidate; } public static void main(String[] args) { int[] id {1, 6, 3, 6, 6, 2, 1, 6, 6, 3, 6, 6, 3, 6, 1, 6}; System.out.printf(The water kind is: %d%n, find(id)); int[] id3 { 1, 5, 1, 88, 3, 2, 3, 2, 3, 3, 3, 2, 6, 9, 99, 3, 2, 1, 1, 1, 2, 1, 3, 3, 2, 1, 66, 6, 3, 1, 1, 2, 11, 1, 2, 3, 2, 2, 2, 3 }; System.out.printf(Afterwards, the big 3 water kings are: %s%n, Arrays.toString(find3(id3))); } } // Output: /* The water kind is: 6 Afterwards, the big 3 water kings are: [3, 2, 1] */