42.最后的胜者

题目概述

题目详情(点我)

现在有n个魔法师(2<=n<=100000)，这n个魔法师都有自己的魔法值ai(1<=ai<=1000000000)，他们为了证明自己是最强的魔法师便开始了争夺战，任意一个魔法师都可以对其他的魔法师发起攻击，每次攻击，被攻击的魔法师损失掉的魔法值是攻击者当前的魔法值，当魔法值小于等于0的时候淘汰出局，问最后只剩下一名魔法师时，他的魔法值最少是多少。

输入:
输入魔法师数n，和n个数，表示每个魔法师的初始魔法值

输出:
输出一个数，在任意的对决中，最后只剩下来一名魔法师的最小的魔法值

题解

解题方法

• 分情况讨论

算法知识

• 数学知识

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

解题思路

审题

• n : 魔法师的个数
• nums : 存储n个魔法师的魔法值
• 魔法值小于等于0直接出局
• 同一时间可以对其他魔法师进行多次攻击

题目要求

• 最后一位魔法师剩的最小魔法值

思路

• 分情况讨论

  • 如果全为偶数

    • 每个数都能和最小值整除, 则返回最小值
    • 否则返回2

  • 如果不全为偶数, 则依次取每个数与最小值进行取余

    • 若结果为0, 则换取下一个数与最小值进行取余, 若全部与最小值min进行取余时, 结果均为0, 则代表当前值为最小值, 返回当前最小值。（最小值min是会改变的）
    • 若结果为1, 则直接返回1
    • 若结果为其他值, 则更新将选取的数设置为最小值, 将最小值设置为取余结果, 并继续进行取余操作, 直到结果为0或为1

步骤

1. 定义变量

   • int min : 用来存储最小值, 初始值为2000000000
   • int ou : 用来存储偶数的个数, 初始值为0

2. 遍历数组nums, 记录偶数的个数 以及 记录最小值

3. 判断是否只有偶数

   • 遍历数组nums, 判断每个值和最小值进行取余后结果是否为0

     • 如果结果不为0的话直接返回2;
     • 主要是为了判断每个数和最小值是否为倍数关系, 若均为倍数关系, 则最后剩下的魔法师上最少的魔法值就为该最小值。

4. 若有偶数和奇数 或 只有奇数

   • 遍历数组nums, 对于每个数nums[i]与最小值进行取余操作

     • 若结果为0, 则表示最小值为当前值的倍数, 则跳出循环, 使用其他数与最小值进行取余操作。
     • 若结果为1, 则直接返回1, 因为1是任何数的倍数
     • 若结果为其他值, 则将当前值nums[i]赋值为min的值, 更新最小值为取余结果, 然后nums[i] 再与最小值进行取余操作。
5. 若遍历结束后, 仍没有返回, 则表示当前最小值min为最后剩余的魔法值。