「生活可以更简单, 欢迎来到我的开源世界」
算法-查找
2020-06-29

学习并记录下查找算法,方便回顾。

第一题:
输入说明:
第一行输入n代表队伍中的人数
第二行输入队伍中每个人的身高(用空格隔开)

比如输入:
5
2 3 1 5 4
6
5 4 1 6 8 2

输出说明:
如果现在所在位置之前没有比自己身高高的,数值变为-1,如果现在所在位置之前有比自己身高高的,数值变为所在位置之前那个离自己最近的且比自己高的那个人的身高

上例的输入对应输出:
5
-1 -1 3 -1 5
6
-1 5 4 -1 -1 8

思路:使用一个数组存放身高,因为每个人都要和前面所有人比较,所以从最后一个人开始,使用二层循环,从后往前修改不影响前面数值的比较。

#include <iostream>

using std::cin;
using std::cout;
using std::endl;


int main(int argc, char* argv[]){
int n;
while(cin >> n){
int *a = new int[n];
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = n-1; i >= 0; i--){
int k = -1;
for(int j = i - 1; j >= 0; j--){
if(a[i] < a[j]){
k = j;
break;
}
}
if(k == -1)a[i] = -1;
else a[i] = a[k];
}
for(int i = 0; i < n; i++)cout << a[i] << ' ';
cout << endl;
delete[] a;
}

return 0;
}
<⇧>