数组与字符串|169. 多数元素 14. 最长公共前缀

169. 多数元素

题目： 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ? n/2 ? 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
题目链接： 169. 多数元素
时间复杂度为 O(n)、空间复杂度为 O(1) 的算法
多种解法：
1.暴力
使用哈希表统计每个元素出现的次数
时间复杂度O(n) 空间复杂度O(n)
2.排序
排序后返回下标为n/2的元素
时间复杂度O(nlogn) 空间复杂度O(1)
3.分治
如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。
将数组分成左右两部分，分别求出左半部分的众数 a1 以及右半部分的众数 a2，随后在 a1 和 a2 中选出正确的众数。
我们使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。
时间复杂度：O(nlog?n)
空间复杂度：O(log?n) （递归带来的空间复杂度）
4.摩尔投票算法
什么是摩尔投票算法
为什么可以用摩尔投票算法
推论一：若记众数的票数为 +1 ，非众数的票数为?1 ，则一定有所有数字的 票数和 >0。
推论二：若数组的前 a个数字的 票数和 =0 ，则 数组剩余 (n?a)个数字的 票数和一定仍 >0 ，即后 (n?a)个数字的 众数仍为 x 。
解题思路：
我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
在遍历完成后，candidate 即为整个数组的众数。

class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int result=0;
        int count=0;
        for(int i=0;i<nums.length;i++){
            if(count==0){
                result=nums[i];
            }
            if(nums[i]==result){
                count++;
            }else{
                count--;
            }
        }
        return result;
        
    }
}

14. 最长公共前缀
**题目：**编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。
题目链接：14. 最长公共前缀

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String common=strs[0];
        int index=0;
        while(index<common.length()){
            for(int i=0;i<strs.length;i++){
                if(index>=strs[i].length()){
                    return common.substring(0,index);
                }
                if(common.charAt(index)!=strs[i].charAt(index)){            
                    if(index==0){
                        return "";
                    }else{
                        return common.substring(0,index);
                    }
                }
            }
            index++;
        }
        String result=common.substring(0,index);
        return result;
    }
}