11.找出常用的数字

目录介绍

• 01.题目要求
• 02.问题分析
• 03.实例代码
• 04.如何优化
• 05.优化代码

01.题目要求

• 问题如下所示：
  • 给你一个长度为n的数组，其中有一个数字出现的次数至少为n/2，找出这个数字
  • 注意，需要的是排序的数组

02.问题分析

• 使用栈的思想来做
  • 如果栈是空的，那么先把数据存进去
  • 然后继续遍历其他的数据，只要发现栈中的数据和遍历中的数据不一样，那么就出栈
  • 如果是相同的，那么就入栈
  • 其实就是捉住数字出现的次数多于数组一半的长度这里入手。如果这个数出现的次数是大于这个数组长度的2/1，那么最后留下的肯定是这个数
• 示例 1:

  输入: [1,1,1,2,5,7,8,8,8,8,10]
  输出: 8

03.实例代码

• 如下所示

  int removeDuplicates(int[] num) {
      if (num==null || num.length==0){
          return 0;
      }
      int currentV = num[0];
      int count = 0;
      for(int i = 1 ; i < num.length; i++){
          if(num[i] != currentV){
              count++;
              currentV = num[i];
              num[count] = currentV;
          }
      }
      return count+1;
  }

04.如何优化

• 其实没必要用整个栈来装载数组，因为使用栈顶元素(出现次数最多的那个),而栈的大小也可以通过一个变量就可以来确定了
• 只要元素相同->入栈(长度+1)。元素不相同-->出栈(长度-1)
• 最终留下来的肯定是出现最频繁的那个数字!

05.优化代码

• 如下所示

  public int findMajorityElement2(int[] arrays) {
      if (arrays==null || arrays.length==0){
          return 0;
      }
      // 装载栈的元素
      int candidate = -1;
      // 栈的大小(长度)
      int count = 0;
      // 遍历给出的数组
      for (int i = 0; i < arrays.length; i++) {
          // 判断该栈为空，那么直接将元素入栈
          if (count == 0) {
              candidate = arrays[i];
              count++;
          } else if (candidate == arrays[i]) {
              // 该元素是否与栈的元素一致-->入栈(栈多一个元素)
              count++;
          } else {
              // 只要不一致-->出栈(栈少一个元素)
              count--;
          }
      }
      // 只要该数字出现次数大于数组长度的2/1，那么留下来的数字肯定在栈顶中
      return candidate;
  }