搜尋
首頁後端開發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:死亡還是簡單地發展?C:死亡還是簡單地發展?Apr 24, 2025 am 12:13 AM

1)c relevantduetoItsAverity and效率和效果臨界。 2)theLanguageIsconTinuellyUped,withc 20introducingFeaturesFeaturesLikeTuresLikeSlikeModeLeslikeMeSandIntIneStoImproutiMimproutimprouteverusabilityandperformance.3)

C在現代世界中:應用和行業C在現代世界中:應用和行業Apr 23, 2025 am 12:10 AM

C 在現代世界中的應用廣泛且重要。 1)在遊戲開發中,C 因其高性能和多態性被廣泛使用,如UnrealEngine和Unity。 2)在金融交易系統中,C 的低延遲和高吞吐量使其成為首選,適用於高頻交易和實時數據分析。

C XML庫:比較和對比選項C XML庫:比較和對比選項Apr 22, 2025 am 12:05 AM

C 中有四種常用的XML庫:TinyXML-2、PugiXML、Xerces-C 和RapidXML。 1.TinyXML-2適合資源有限的環境,輕量但功能有限。 2.PugiXML快速且支持XPath查詢,適用於復雜XML結構。 3.Xerces-C 功能強大,支持DOM和SAX解析,適用於復雜處理。 4.RapidXML專注於性能,解析速度極快,但不支持XPath查詢。

C和XML:探索關係和支持C和XML:探索關係和支持Apr 21, 2025 am 12:02 AM

C 通過第三方庫(如TinyXML、Pugixml、Xerces-C )與XML交互。 1)使用庫解析XML文件,將其轉換為C 可處理的數據結構。 2)生成XML時,將C 數據結構轉換為XML格式。 3)在實際應用中,XML常用於配置文件和數據交換,提升開發效率。

C#vs. C:了解關鍵差異和相似之處C#vs. C:了解關鍵差異和相似之處Apr 20, 2025 am 12:03 AM

C#和C 的主要區別在於語法、性能和應用場景。 1)C#語法更簡潔,支持垃圾回收,適用於.NET框架開發。 2)C 性能更高,需手動管理內存,常用於系統編程和遊戲開發。

C#與C:歷史,進化和未來前景C#與C:歷史,進化和未來前景Apr 19, 2025 am 12:07 AM

C#和C 的歷史與演變各有特色,未來前景也不同。 1.C 由BjarneStroustrup在1983年發明,旨在將面向對象編程引入C語言,其演變歷程包括多次標準化,如C 11引入auto關鍵字和lambda表達式,C 20引入概念和協程,未來將專注於性能和系統級編程。 2.C#由微軟在2000年發布,結合C 和Java的優點,其演變注重簡潔性和生產力,如C#2.0引入泛型,C#5.0引入異步編程,未來將專注於開發者的生產力和雲計算。

C#vs. C:學習曲線和開發人員的經驗C#vs. C:學習曲線和開發人員的經驗Apr 18, 2025 am 12:13 AM

C#和C 的学习曲线和开发者体验有显著差异。1)C#的学习曲线较平缓,适合快速开发和企业级应用。2)C 的学习曲线较陡峭,适用于高性能和低级控制的场景。

C#vs. C:面向對象的編程和功能C#vs. C:面向對象的編程和功能Apr 17, 2025 am 12:02 AM

C#和C 在面向对象编程(OOP)中的实现方式和特性上有显著差异。1)C#的类定义和语法更为简洁,支持如LINQ等高级特性。2)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脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強大的PHP整合開發環境

MantisBT

MantisBT

Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

記事本++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),