Day6

多数元素

1. 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于$ ⌊ n/2 ⌋$ 的元素。

   你可以假设数组是非空的，并且给定的数组总是存在多数元素。例如：

输入：[3, 2, 3]
输出：3

2. 题目解析，此题目做法较多，可以采用如下做法：

   • 哈希表法，维护一个哈希表计算其中元素的个数，并选择个数多于 n/2 的为众数，空间复杂度较高
   • 分治法，当一个数组被分解成为左右部分，肯定左右部分的一个众数会是整个数组的众数，不然的话 $ < \frac{1}{2} l + \frac{1}{2} r $ 不可能成为众数。代码如下：

   class Solution {
       public int majorityElement(int[] nums) {
           return merge(nums, 0, nums.length - 1);
       }
       //统计两左右数组相合的数的出现次数
       public int countNumber(int []nums, int l, int r, int num){
           int count = 0;
           for(int i = l; i <= r; i ++){
               count += (num == nums[i]) ? 1 : 0;
           }
           return count;
       }
       public int merge(int[] nums, int l, int r){
           if(l == r)
               return nums[l];
           int mid = l + r >> 1;
           int left = merge(nums, l, mid);
           int right = merge(nums, mid + 1, r);
   
           //当左数组和右数组的众数相等，则返回其众数，否则统计左右众数在整个区间内出现的次数，并以大的为众数
           if(left == right)
               return left;
           int leftCount = countNumber(nums, l, r, left);
           int rightCount = countNumber(nums, l, r, right);
           return leftCount >= rightCount ? left : right; 
       }
   }
   

   • 摩尔投票法，摩尔投票的原理主要是：一个数是众数，即它的统计次数大于 \(\frac{n}{2}\) ，那么与其他非众数的数两两消耗时，他必定能最后存活下来。所以代码如下：

   class Solution {
       public int majorityElement(int[] nums) {
           int count = 0;
           Integer val = null;
           for(int num : nums){
               if(count == 0)
                   val = num;
               count += (num == val) ? 1 : -1;
           }
       }
   }
   

二叉树的最大深度

1. 题目：求得一棵树的最大深度
2. 题目解析：题目较为简单，可以联系求二叉树直径的题目进行理解，代码如下：

class Solution {
    public int maxDepth(TreeNode root) {
        return depth(root);
    }
    public int depth(TreeNode root){
        if(root == null)
            return 0;
        //返回左子树和右子树最大的节点数目再加上 1 即可
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

根据前序和中序遍历创建树

1. 题目：给定一棵树的前序和中序遍历的数组，创建一棵二叉树。

输入：前序遍历 = [3, 9, 20, 15, 7]
      中序遍历 = [9, 3, 15, 20, 7]
输出：	3
      /  \
     9   20
        /  \
       15   7 

2. 题目解析：根据树的性质很轻松的想到递归的思路，即分治思维，首先创建好树根节点，再创建每一棵树的左右子树，根据代码理解题意。代码如下

class Solution {
    //前序遍历的序列号，由于创建节点的过程中，前序数组每一次的移动都是根节点的所在位置
    public int index = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0)
            return null;
        //创建中序遍历数组的数值和元素索引之间的对应关系，降低时间复杂度
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < inorder.length; i ++)
            map.put(inorder[i], i);
        return build(preorder, inorder, 0, inorder.length - 1, map);
    }
    public TreeNode build(int[] preorder, int[] inorder, int l, int r, Map<Integer,          Integer> map){
        //递归终止条件，当左边界大于右边界时返回 null
        if(l > r)
            return null;
        //取出根节点的值，并让 index 向前一步
        int cnt = preorder[index ++];
        TreeNode root = new TreeNode(cnt);
        //寻找根节点在中序遍历数组中的位置，并将其划分为左右两部分的数组，进行左右子树的创建
        int mid = map.get(cnt);
        root.left = build(preorder, inorder, l, mid - 1, map);
        root.right = build(preorder, inorder, mid + 1, r, map);
        return root;
    }
}