在這個問題中,我們透過每輪執行給定的操作將陣列大小減少到 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中文網其他相關文章!

本文詳細介紹了C函數返回類型,包括基本(int,float,char等),派生(數組,指針,結構)和void類型。 編譯器通過函數聲明和返回語句確定返回類型,執行

Gulc是一個高性能的C庫,優先考慮最小開銷,積極的內襯和編譯器優化。 其設計非常適合高頻交易和嵌入式系統等關鍵應用程序,其設計強調簡單性,模型

本文解釋了C函數聲明與定義,參數傳遞(按值和指針),返回值以及常見的陷阱,例如內存洩漏和類型不匹配。 它強調了聲明對模塊化和省份的重要性

本文詳細介紹了字符串案例轉換的C功能。 它可以通過ctype.h的toupper()和tolower()解釋,並通過字符串迭代並處理零終端。 常見的陷阱,例如忘記ctype.h和修改字符串文字是

本文研究C函數返回值存儲。 較小的返回值通常存儲在寄存器中以備速度;較大的值可能會使用指針來記憶(堆棧或堆),影響壽命並需要手動內存管理。直接ACC

本文分析了形容詞“獨特”的多方面用途,探索其語法功能,常見的短語(例如,“不同於”,“完全不同”),以及在正式與非正式中的細微應用

本文解釋了C標準模板庫(STL),重點關注其核心組件:容器,迭代器,算法和函子。 它詳細介紹了這些如何交互以啟用通用編程,提高代碼效率和可讀性t

本文詳細介紹了c中有效的STL算法用法。 它強調了數據結構選擇(向量與列表),算法複雜性分析(例如,std :: sort vs. std vs. std :: partial_sort),迭代器用法和並行執行。 常見的陷阱


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

DVWA
Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

SecLists
SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

Atom編輯器mac版下載
最受歡迎的的開源編輯器

ZendStudio 13.5.1 Mac
強大的PHP整合開發環境