資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 查詢陣列中最後一個移除元素的位置
在這個問題中，我們給定一個大小為 N 的陣列 arr[] 和一個整數 M。我們的任務是查詢陣列中最後一個移除元素的位置。
陣列中值的移除基於以下操作：
- 對於陣列中的元素 arr[i]。如果 arr[i] > M，則彈出該值並將 arr[i] - M 推送到陣列的末尾。否則將其從陣列中移除。
執行這些操作，直到陣列僅包含元素。
讓我們舉一個例子來理解這個問題：
輸入
arr[] = {5, 4, 8}, M = 3輸出
3
解釋
Removing values using operations,
{5, 4, 8} -> {4, 8, 2} -> {8, 1, 2} -> {1, 2, 5} -> {2, 5} -> {5} -> {2} ->
empty array.
The last value removed is 8, position is 3.解決方案方法
解決這個問題的一個簡單方法是利用以下事實：每個最後移除的值都具有ceil(arr[i] / M)的最大值，從而找到最後一個移除的值。
為了找到最後退出陣列的元素的位置，我們將遍歷陣列並存儲具有ceil(arr[i] / M)最大值的元素的位置。
示例
程式說明我們解決方案的工作原理
#include <iostream>
using namespace std;
int findLastRemPos(int arr[], int n, int m){
for (int i = 0; i < n; i++) {
arr[i] = (arr[i] / m + (arr[i] % m != 0));
}
int lastRemPos = -1, largestVal = -1;
for (int i = n - 1; i >= 0; i--) {
if (largestVal < arr[i]) {
largestVal = arr[i];
lastRemPos = i;
}
}
return lastRemPos + 1;
}
int main(){
int arr[] = {5, 4, 8, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int m = 3;
cout<<"The position of last removed element in the array is "<<findLastRemPos(arr, n, m);
return 0;
}輸出
The position of last removed element in the array is 3
更新於: 2022年2月11日
104 次檢視
廣告