当前位置: 首页 > article >正文

Leetcode3266. K 次乘运算后的最终数组 II

Every day a Leetcode

题目来源:3266. K 次乘运算后的最终数组 II

解法1:3266. K 次乘运算后的最终数组 II

用最小堆手动模拟操作,直到原数组的最大值 mx 成为这 n 个数的最小值。

设此时还剩下 k 次操作,那么:

  • 对于前 k mod n 小的数,还可以再操作 k/n+1 次。
  • 其余元素,还可以再操作 k/n 次。

用快速幂计算操作这么多次后的结果。

代码:

/*
 * @lc app=leetcode.cn id=3266 lang=cpp
 *
 * [3266] K 次乘运算后的最终数组 II
 */

// @lc code=start
class Solution
{
private:
    const int MOD = 1e9 + 7;
    // 快速幂
    long long pow(long long x, int n)
    {
        long long res = 1;
        for (; n; n /= 2)
        {
            if (n % 2)
                res = res * x % MOD;
            x = x * x % MOD;
        }
        return res;
    }

public:
    vector<int> getFinalState(vector<int> &nums, int k, int multiplier)
    {
        // 特判
        if (multiplier == 1)
            return move(nums);

        int n = nums.size();
        int mx = *max_element(nums.begin(), nums.end());
        vector<pair<long long, int>> h(n);
        for (int i = 0; i < n; i++)
        {
            h[i] = {nums[i], i};
        }
        ranges::make_heap(h, greater<>()); // 最小堆,O(n) 堆化

        // 模拟,直到堆顶是 mx
        for (; k && h[0].first < mx; k--)
        {
            ranges::pop_heap(h, greater<>());
            h.back().first *= multiplier;
            ranges::push_heap(h, greater<>());
        }

        // 剩余的操作可以直接用公式计算
        ranges::sort(h);
        for (int i = 0; i < n; i++)
        {
            auto &[x, j] = h[i];
            nums[j] = x % MOD * pow(multiplier, k / n + (i < k % n)) % MOD;
        }
        return move(nums);
    }
};
// @lc code=end

结果:

在这里插入图片描述

复杂度分析:

时间复杂度:O(n * logn * logmU),其中 n 是数组 nums 的长度,U=max(nums),m=multiplier。

空间复杂度:O(n),其中 n 是数组 nums 的长度。


http://www.kler.cn/a/298974.html

相关文章:

  • MySQL深度解析:高效查询优化与实战案例
  • Unity全局雾效
  • 随手记:小程序兼容后台的wangEditor富文本配置链接
  • 新版国标GB28181设备端Android版EasyGBD支持国标GB28181-2022,支持语音对讲,支持位置上报,开源在Github
  • 基于Spring Boot的智慧农业专家远程指导系统
  • MySQL 分区与分表策略
  • 【Nacos】健康检查与环境隔离
  • 【数据结构】2——二叉树遍历
  • 用hiredis连接redis
  • 如何优化谷歌排名更有效?
  • Linux之Shell命令
  • 【YouTube采集】按搜索关键词批量爬取视频数据,并封装成exe界面软件!
  • ubuntu使用命令行查看硬件信息
  • STM32 的 CAN 通讯全攻略
  • io多路复用
  • cross-plateform 跨平台应用程序-06-uni-app 介绍
  • Spring Boot 执行流程已经 负载均衡执行流程图
  • java实现文本相似度计算
  • 基于C#的UDP协议消息传输
  • sql中索引查看是否生效
  • 计算机网络 --- 【1】欢迎来到计算机网络/计算机网络基本概念/计算机网络、互连网、互联网的区别
  • Springcould -第一个Eureka应用 --- day02
  • Apache POI用法
  • [网鼎杯 2020 朱雀组]Nmap 历程记录
  • Java 远程执行服务器上的命令
  • HP电脑如何启动硬件检测