分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter
package live.every.day.ProgrammingDesign.CodingInterviewGuide.ArrayAndMatrix; /** * 在数组中找到出现次数大于N/K的数 * * 【题目】 * 给定一个整型数组arr，打印其中出现次数大于一半的数，如果没有这样的数，打印提示信息。 * * 【进阶】 * 给定一个整型数组arr，再给定一个整数K，打印所有出现次数大于N/K的数，如果没有这样的数，打印提示信息。 * * 【要求】 * 原问题要求时间复杂度为O(N)，额外空间复杂度为O(1)。进阶问题要求时间复杂度为O(NxK)，额外外空间复杂度为O(K)。 * * 【难度】 * 困难 * * 【解答】 * 无论是原问题还是进阶问题，都可以用哈希表记录每个数及其出现的次数，但是额外空间复杂度为O(N)，不符合题目要求，所以本文 * 不再详述这种简单的方法。本文提供方法的核心思路是，一次在数组中删掉K个不同的数，不停地删除，直到剩下数的种类不足K就停止 * 删除，那么，如果一个数在数组中出现的次数大于N/K，则这个数最后一定会被剩下来。 * * 对于原问题，出现次数大于一半的数最多只会有一个，还可能不存在这样的数。具体的过程为，一次在数组中删掉两个不同的数，不停 * 地删除，直到剩下的数只有一种，如果一个数出现次数大于一半，这个数最后一定会剩下来。如下代码中的printHalfMajor方法就 * 是这种思路的具体实现，我们先列出代码，然后进行解释。 * * printHalfMajor方法中第一个for循环就是一次在数组中删掉两个不同的数的代码实现。我们把变量cand叫作候选，times叫作次 * 数，读者先不用纠结这两个变量是什么意义，我们看在第一个for循环中发生了什么。 * •times==0时，表示当前没有候选，则把当前数arr[i]设成候选，同时把times设置成1。 * •times!=0时，表示当前有候选，如果当前的数arr[i]与候选一样，就把times加1；如果当前的数arr[i]与候选不一样，就把 * times减1，减到0则表示又没有候选了。 * * 这具体是什么意思呢？当没有候选时，我们把当前的数作为候选，说明我们找到了两个不同的数中的第一个；当有候选且当前的数和候 * 选一样时，说明目前没有找到两个不同的数中的另外一个，反而是同一种数反复出现了，那么就把times++表示反复出现的数在累计自 * 己的点数。当有候选且当前的数和候选不一样时，说明找全了两个不同的数，但是候选可能在之前多次出现，如果此时把候选完全换掉， * 候选的这个数相当于一下被删掉了多个，对吧？所以这时候选"付出"一个自己的点数，即times减1，然后当前数也被删掉。这样还是 * 相当于一次删掉了两个不同的数。当然，如果times被减到为0，说明候选的点数完全被消耗完，那么又表示候选空缺，arr中的下一个 * 数(arr[i+1])就又被作为候选。 * 综上所述，第一个for循环的实质就是我们的核心解题思路，一次在数组中删掉两个不同的数，不停地删除，直到剩下的数只有一种， * 如果一个数出现次数大于一半，则这个数最后一定会被剩下来，也就是最后的cand值。 * 这里请注意一点，一个数出现次数虽然大于一半，它肯定会被剩下来，但那并不表示剩下来的数一定是符合条件的。例如，1，2，1。 * 其中1符合出现次数超过了一半，所以1肯定会剩下来。再如1，2，3，其中没有任何一个数出现的次数超过了一半，可3最后也剩下来 * 了。所以printHalfMajor方法中第二个for循环的工作就是检验最后剩下来的那个数(即cand)是否真的是出现次数大于一半的数。 * 如果cand都不符合条件，那么其他的数也一定都不符合，说明arr中没有任何一个数出现了一半以上。 * * 【扩展】 * 这种一次删掉大个不同的数的思想在面试中通常会变形之后反复出现。例如，下面这道面试真题：有一场投票，投票有效的条件是必须 * 有一个候选人得票数超过半数，但是验票人员不能看到每张选票上选了谁，只能把任意两张选票放到一台机器上看这两张选票是否一 * 样，若一样，则机器给出true的提醒，不一样则给出false的提醒。如果你作为验票的人员，怎么判断这场投票是有效的？ * 这道题目就是原问题的变形，但是"不能看到每张选票上选了谁"的这个限制实际上把用哈希表来解题的可能性完全堵死了。但本文的方 * 法却可以满足题目的要求，因为我们实现的方法只需要当前数和候选数做比较，而不需要知道每个数的值。 * * @author Created by LiveEveryDay */ public class InArrayFindAppearTimeGreaterThanNK1 { public static void printHalfMajor(int[] arr) { int cand = 0; int times = 0; for (int i = 0; i != arr.length; i++) { if (times == 0) { cand = arr[i]; times = 1; } else if (arr[i] == cand) { times++; } else { times--; } } times = 0; for (int i = 0; i != arr.length; i++) { if (arr[i] == cand) { times++; } } if (times > arr.length / 2) { System.out.println(cand); } else { System.out.println("No such number."); } } public static void main(String[] args) { int[] arr = {1, 8, 3, 8, 2, 8, 8}; printHalfMajor(arr); } } // ------ Output ------ /* 8 */
