数据结构
网络
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 次查看
广告