2020年06月25日

数组

多数投票算法（Majority Vote Algorithm）。 给一个数组，其中含有N个非负元素，让你求出数组中出现次数超过一半的数字。（排序的时间复杂度一般来说是O(NlogN)，那么有没有时间复杂度为n的算法呢？ ） 设置一个计数器count和保存最多元素的变量majority，

如果count==0，则将now的值设置为数组的当前元素，将majority赋值为1；反之，如果majority和现在数组元素值相同，则count++，反之count–；重复上述两步，直到扫描完数组。count赋值为0，再次从头扫描数组，如果素组元素值与majority的值相同则count++，直到扫描完数组为止。如果此时count的值大于等于n/2，则返回majority的值，反之则返回-1。

优秀代码参考

ID题目大致内容解题思想注意点228汇总区间双指针229求众数 II投票算法。明确一点，n/k的众数最多只有k-1个。因为假设有k个众数，个数>(n/k * k),得>n,显然不成立。代码分三步走：1、如果投A（当前元素等于A），则A的票数++; 2、如果投B（当前元素等于B），B的票数++； 3、如果A,B都不投（即当前与A，B都不相等）,那么检查此时A或B的票数是否减为0，如果为0,则当前元素成为新的候选人；如果A,B两个人的票数都不为0，那么A,B两个候选人的票数均减一。遍历结束后选出了两个候选人，但是这两个候选人是否满足>n/3，还需要再遍历一遍数组，找出两个候选人的具体票数。238除自身以外数组的乘积方法一：左右乘积列表 利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。方法二：空间复杂度 O(1) 的方法 将 L 或 R 数组用输出数组来计算。先把输出数组当作 L 数组来计算，然后再动态构造 R 数组得到结果287寻找重复数二分法，用到抽屉原理，10个苹果放进9个抽屉，肯定至少有一个抽屉不少于2个苹果。有效范围 [left, right]里的中间数 mid，统计原始数组中小于等于这个中间数的元素的个数 cnt，如果 cnt 严格大于 mid，根据抽屉原理，重复元素就在区间 [left, mid] 里。289生命游戏先将下次状态变成1的0赋值-1，将下次状态变为0的2赋值-2。再遍历把-1和-2分别变回1和0。

常用方法积累

类名方法名解释ArrayListindexOf(value)返回value值对应的索引值，ArrayListcopyOfRange(T[ ] original,int from,int to)将原数组original，从下标from开始复制，复制到上标to，生成一个新的数组。ArrayListans.get(i).append©名为ans的ArrayList对象拿出索引i处的元素，并在其后追加一个字符或数字c。注意不是[index]HashMapgetOrDefault(Object key, V defaultValue)当Map集合中有这个key时，就使用对应的value值，如果没有就使用默认值defaultValueMapentrySet()获取所有key和value，遍历的时候用，例子：for (Map.Entry<String, String> entry : map.entrySet()) {System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());}IntegertoBinaryString(num)返回num整数的二进制字符串表达IntegertoHexString(num)返回num整数的十六进制字符串表达IntegerbitCount(num)返回num整数的二进制表达式中1的个数CharactertoLowerCase©返回c的字母小写形式CharactertoUpperCase©返回c的字母大写形式CharacterisLetter©判断c是否为字母Stringformat(patten,num)格式化字符串，比如format("%d:d",1,2),输出结果为1:02StringsubString(start,end)含start，不含endStringBuilderdeleteCharAt(index删除索引所在处的字符Arraysfill(Object[] a, Object val)再数组a中把所有值都填充为valArraysequals(s1,s2)比较两个数组元素是否相同ArraysasList(s1,…,sn)将一个数组s1,…,sn转换为 List.注意，数组元素不能是原生数据类型(int,long等)，要用其包装类Integer等Arraysset(index,element)修改列表中的值。（index指定下标，element指定要修改后元素的值）SystemarrayCopy(Object src, int srcPos, Object dest, int destPos, int length)Object src : 原数组; int srcPos:从元数据的起始位置开始; Object dest:目标数组; int destPos:目标数组的开始起始位置; int length:要copy的数组的长度TreeSetfloor(E e)返回在这个集合中小于或者等于给定元素的最大元素，如果不存在这样的元素,返回null.TreeSetceiling(E e)返回在这个集合中大于或者等于给定元素的最小元素，如果不存在这样的元素,返回null.

参考

leetcode-jerry_nju博客- 多数投票算法Majority Vote Algorithmleetcode-liweiwei1419