搜索
首页后端开发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#vs. C:面向对象的编程和功能C#vs. C:面向对象的编程和功能Apr 17, 2025 am 12:02 AM

C#和C 在面向对象编程(OOP)中的实现方式和特性上有显着差异。 1)C#的类定义和语法更为简洁,支持如LINQ等高级特性。 2)C 提供更细粒度的控制,适用于系统编程和高性能需求。两者各有优势,选择应基于具体应用场景。

从XML到C:数据转换和操纵从XML到C:数据转换和操纵Apr 16, 2025 am 12:08 AM

从XML转换到C 并进行数据操作可以通过以下步骤实现:1)使用tinyxml2库解析XML文件,2)将数据映射到C 的数据结构中,3)使用C 标准库如std::vector进行数据操作。通过这些步骤,可以高效地处理和操作从XML转换过来的数据。

C#vs. C:内存管理和垃圾收集C#vs. C:内存管理和垃圾收集Apr 15, 2025 am 12:16 AM

C#使用自动垃圾回收机制,而C 采用手动内存管理。1.C#的垃圾回收器自动管理内存,减少内存泄漏风险,但可能导致性能下降。2.C 提供灵活的内存控制,适合需要精细管理的应用,但需谨慎处理以避免内存泄漏。

超越炒作:评估当今C的相关性超越炒作:评估当今C的相关性Apr 14, 2025 am 12:01 AM

C 在现代编程中仍然具有重要相关性。1)高性能和硬件直接操作能力使其在游戏开发、嵌入式系统和高性能计算等领域占据首选地位。2)丰富的编程范式和现代特性如智能指针和模板编程增强了其灵活性和效率,尽管学习曲线陡峭,但其强大功能使其在今天的编程生态中依然重要。

C社区:资源,支持和发展C社区:资源,支持和发展Apr 13, 2025 am 12:01 AM

C 学习者和开发者可以从StackOverflow、Reddit的r/cpp社区、Coursera和edX的课程、GitHub上的开源项目、专业咨询服务以及CppCon等会议中获得资源和支持。1.StackOverflow提供技术问题的解答;2.Reddit的r/cpp社区分享最新资讯;3.Coursera和edX提供正式的C 课程;4.GitHub上的开源项目如LLVM和Boost提升技能;5.专业咨询服务如JetBrains和Perforce提供技术支持;6.CppCon等会议有助于职业

c#vs. c:每种语言都擅长c#vs. c:每种语言都擅长Apr 12, 2025 am 12:08 AM

C#适合需要高开发效率和跨平台支持的项目,而C 适用于需要高性能和底层控制的应用。1)C#简化开发,提供垃圾回收和丰富类库,适合企业级应用。2)C 允许直接内存操作,适用于游戏开发和高性能计算。

继续使用C:耐力的原因继续使用C:耐力的原因Apr 11, 2025 am 12:02 AM

C 持续使用的理由包括其高性能、广泛应用和不断演进的特性。1)高效性能:通过直接操作内存和硬件,C 在系统编程和高性能计算中表现出色。2)广泛应用:在游戏开发、嵌入式系统等领域大放异彩。3)不断演进:自1983年发布以来,C 持续增加新特性,保持其竞争力。

C和XML的未来:新兴趋势和技术C和XML的未来:新兴趋势和技术Apr 10, 2025 am 09:28 AM

C 和XML的未来发展趋势分别为:1)C 将通过C 20和C 23标准引入模块、概念和协程等新特性,提升编程效率和安全性;2)XML将继续在数据交换和配置文件中占据重要地位,但会面临JSON和YAML的挑战,并朝着更简洁和易解析的方向发展,如XMLSchema1.1和XPath3.1的改进。

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.能量晶体解释及其做什么(黄色晶体)
1 个月前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
1 个月前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
1 个月前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.聊天命令以及如何使用它们
1 个月前By尊渡假赌尊渡假赌尊渡假赌

热工具

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能

WebStorm Mac版

WebStorm Mac版

好用的JavaScript开发工具

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境