搜索
首页后端开发C++通过给定的操作将数组减少到最多一个元素

通过给定的操作将数组减少到最多一个元素

在这个问题中,我们通过每轮执行给定的操作将数组大小减少到 1 或 0。

我们可以在每一轮中对数组进行排序,以获得每次迭代中的最大元素。另外,我们还可以使用head数据结构来提高代码的性能。

问题陈述 - 我们给出了一个 nums[] 数组。我们需要通过执行以下操作来减少数组。

  • 选择数组中两个最大元素。

  • 如果两个元素相同,则从数组中删除这两个元素。

  • 如果两个元素不相同,则从数组中删除这两个元素,并将abs(first − secondary)插入数组中。

打印数组的最后一个元素。如果数组为空,则打印 0。

示例

输入

nums = {5, 9, 8, 3, 2, 5};

输出

0

说明

  • 在第一轮中,我们取 9 和 8 并将其差值添加到数组中。因此,数组变为 [5, 3, 2, 5, 1]。

  • 在第二轮中,我们取 5 和 5。因此,数组变为 [3, 2, 1]。

  • 下一轮,我们取 3 和 2。因此,数组变为 [1, 1]

  • 在最后一轮中,我们取 1 和 1。因此,数组变为空,我们打印 0。

输入

nums = {5, 5, 5, 5, 5};

输出

5

解释- 我们两次删除一对 5,并且有一个 5 保留在数组中。

输入

nums = {4, 8, 7, 6};

输出

1

解释 - 首先,我们选择 8 和 7。因此,数组变为 [4, 1, 6]。之后,我们选择4和6。因此,数组变为[1, 2]。在最后一次操作中,数组变为[1]。

方法 1

在这种方法中,我们将遍历数组,直到数组的大小变为 1 或 0。在每次迭代中,我们将对数组进行排序并对已排序数组的前 2 个元素执行给定的操作。最后,我们将根据数组大小打印输出。

算法

第 1 步- 将数组的大小存储在“len”变量中。

步骤 2- 开始使用 while 循环遍历数组。

第 3 步- 在循环中使用 sort() 方法对数组进行相反的排序。

第 4 步- 获取数组的第一个和第二个元素。另外,计算数组的第一个和第二个元素之间的差异。

第 5 步− 如果差值为 0,则删除数组的前两个元素,并将 'len' 减少 2。如果差值不为 0,则删除前 2 个元素并减少'len' 减 1。

第6步- 最后,如果数组的大小为0,则返回0。否则,返回数组的第一个元素。

示例

#include <bits/stdc++.h>
using namespace std;

int findLast(vector<int> &nums) {
    int len = nums.size();
    int p = 0;
    while (len > 1) {
        // Sort array in reverse order
        sort(nums.begin(), nums.end(), greater<int>());
        // Take the first and second elements of the array
        int a = nums[0];
        int b = nums[1];
        // Take the difference between the first and second element
        int diff = a - b;
        if (diff == 0) {
            nums.erase(nums.begin());
            nums.erase(nums.begin());
            len -= 2;
        } else {
            nums.erase(nums.begin());
            nums.erase(nums.begin());
            nums.push_back(diff);
            len -= 1;
        }
    }
    // When the size of the array is 0
    if (nums.size() == 0)
        return 0;
    return nums[0];
}
int main() {
    vector<int> nums = {5, 9, 8, 3, 2, 5};
    cout << "The last remaining element after performing the given operations is " << findLast(nums) << "\n";
    return 0;
}

输出

The last remaining element after performing the given operations is 0

时间复杂度 - O(N*NlogN),其中 O(N) 用于遍历数组,O(NlogN) 用于在每次迭代中对数组进行排序。

空间复杂度 - O(N) 对数组进行排序。

方法2

在这种方法中,我们将使用优先级队列,它实现了堆数据结构。它始终按排序顺序存储元素。因此,我们可以轻松删除前 2 个最大元素。

算法

第 1 步- 定义名为优先级队列的“p_queue”。

步骤 2- 将所有数组元素插入优先级队列。

步骤 3- 进行迭代,直到优先级队列的大小大于 1。

步骤 4- 逐一删除优先级队列的前 2 个元素。

第 5 步- 求两个元素之间的差异。

第6步- 如果差值不为0,则将其推入优先级队列。

第 7 步− 最后,如果队列大小为 0,则返回 0。

第 8 步- 否则,返回队列顶部的元素。

示例

#include <bits/stdc++.h>
using namespace std;

int findLast(vector<int> &nums) {
    // Defining a priority queue
    priority_queue<int> p_queue;
    // Inserting array elements in priority queue
    for (int p = 0; p < nums.size(); ++p)
        p_queue.push(nums[p]);
    // Make iterations
    while (p_queue.size() > 1) {
        // Take the first element from queue
        int first = p_queue.top();
        p_queue.pop();
        // Get the second element from queue
        int second = p_queue.top();
        p_queue.pop();
        // Take the difference of first and second elements
        int diff = first - second;
        if (diff != 0)
            p_queue.push(diff);
    }
    // When queue is empty
    if (p_queue.size() == 0)
        return 0;
    // Return the last remaining element
    return p_queue.top();
}
int main() {
    vector<int> nums = {5, 9, 8, 3, 2, 5};
    cout << "The last remaining element after performing the given operations is " << findLast(nums) << "\n";
    return 0;
}

输出

The last remaining element after performing the given operations is 0

时间复杂度 - 在优先级队列中插入和删除元素的时间复杂度为 O(NlogN)。

空间复杂度 - 在优先级队列中存储元素的 O(N)。

当我们在插入或删除任何元素后需要按特定顺序排列数组数据时,优先级队列数据结构总是有用的。它实现了堆数据结构,从而实现了插入和删除。

以上是通过给定的操作将数组减少到最多一个元素的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:tutorialspoint。如有侵权,请联系admin@php.cn删除
C标准模板库(STL)如何工作?C标准模板库(STL)如何工作?Mar 12, 2025 pm 04:50 PM

本文解释了C标准模板库(STL),重点关注其核心组件:容器,迭代器,算法和函子。 它详细介绍了这些如何交互以启用通用编程,提高代码效率和可读性t

如何有效地使用STL(排序,查找,转换等)的算法?如何有效地使用STL(排序,查找,转换等)的算法?Mar 12, 2025 pm 04:52 PM

本文详细介绍了c中有效的STL算法用法。 它强调了数据结构选择(向量与列表),算法复杂性分析(例如,std :: sort vs. std vs. std :: partial_sort),迭代器用法和并行执行。 常见的陷阱

我如何在C中有效处理异常?我如何在C中有效处理异常?Mar 12, 2025 pm 04:56 PM

本文详细介绍了C中的有效异常处理,涵盖了尝试,捕捉和投掷机制。 它强调了诸如RAII之类的最佳实践,避免了不必要的捕获块,并为强大的代码登录例外。 该文章还解决了Perf

如何使用C中的移动语义来提高性能?如何使用C中的移动语义来提高性能?Mar 18, 2025 pm 03:27 PM

本文讨论了使用C中的移动语义来通过避免不必要的复制来提高性能。它涵盖了使用std :: Move的实施移动构造函数和任务运算符,并确定了关键方案和陷阱以有效

在C中如何有效地使用RVALUE参考?在C中如何有效地使用RVALUE参考?Mar 18, 2025 pm 03:29 PM

文章讨论了在C中有效使用RVALUE参考,以进行移动语义,完美的转发和资源管理,重点介绍最佳实践和性能改进。(159个字符)

如何在C 20中使用范围进行更有表现的数据操纵?如何在C 20中使用范围进行更有表现的数据操纵?Mar 17, 2025 pm 12:58 PM

C 20范围通过表现力,合成性和效率增强数据操作。它们简化了复杂的转换并集成到现有代码库中,以提高性能和可维护性。

动态调度如何在C中起作用,如何影响性能?动态调度如何在C中起作用,如何影响性能?Mar 17, 2025 pm 01:08 PM

本文讨论了C中的动态调度,其性能成本和优化策略。它突出了动态调度会影响性能并将其与静态调度进行比较的场景,强调性能和之间的权衡

C的内存管理如何工作,包括新,删除和智能指针?C的内存管理如何工作,包括新,删除和智能指针?Mar 17, 2025 pm 01:04 PM

C内存管理使用新的,删除和智能指针。本文讨论了手册与自动化管理以及智能指针如何防止内存泄漏。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),