45.最活跃的数 - 图1

题目概述

题目详情(点我)

现有一个包含n个整数的序列(1<=n<=1e5)，n个数分别是a1,a2,a3…an(0<=ai<=1e5)，现在对于每个ai都有3种操作，一种是使ai+1，一种是使ai-1，还有一种是不变，问在对这n个数操作完后，出现次数最多的数的出现次数是多少。

输入:
输入序列中整数个数n，和n个整数[a1,a2,…,an]

输出:
输出一个数，表示在操作过后的出现次数最多的数的出现次数

题解

解题方法

  • 数组的运用

算法知识

  • 计数

    • 时间复杂度: n
    • 空间复杂度: n

解题思路

审题

  • int n : n个数
  • int nums : 存储n个数

  • 对每个数都能进行3种操作:

    • +1
    • 不变
    • -1

题目要求

  • 对每个数进行操作后, 出现次数最多的数的出现次数

思路

  • 依题意得(⊙ˍ⊙): 要求的值为 连续的三个数的最大出现次数,
    此时这个数就是这三个数的中间值, 然后比它小1的数都+1, 比它大1的数都-1.

  • 既然要统计每个数字出现的次数, 使用数组下标表示数字, 对应的值表示出现的次数, 这样就成功的统计出了每个数出现的次数。

步骤

  1. 定义变量数组

    • int[] arr, 定义空间为100000的数组，用来存储每个数字出现的次数, 初始化均为0
    • int result, 用来存储结果变量的值。初始化为0

  2. 遍历nums数组, 统计每个数字出现的次数

    • arr[num[i]]++;

  3. 从1开始遍历arr数组, 计算出result的值

    • 如果连续三个数出现的次数之和大于result, 则更新result的值。
  4. 返回result