淘宝客的wordpress模板下载地址,seo发布网站,ui培训设计培训班,上海app外包公司1. 题目
某交友网站会给除了第一个用户以外的每个新注册的用户推荐一位之前已经注册过并且性格值和他最相近的用户#xff0c;如果有多人满足条件则选择性格值较小的。
给定数组val[]表示按时间顺序注册的 n 位用户的性格值#xff0c;输出一个大小为 n-1 的数组#xff0…1. 题目
某交友网站会给除了第一个用户以外的每个新注册的用户推荐一位之前已经注册过并且性格值和他最相近的用户如果有多人满足条件则选择性格值较小的。
给定数组val[]表示按时间顺序注册的 n 位用户的性格值输出一个大小为 n-1 的数组表示系统给这些人推荐的用户的性格值。
样例 1:
输入: val[8,9,7,3,0,5,11]
输出: [8,8,7,3,3,9]
解释:
令 ans []
第 2 个数为 9前面只有第 1 个数 8此时 ans [8]
第 3 个数为 7前面的数有 8, 9与 7 性格值最小的为 8此时 ans [8, 8]
第 4 个数为 3前面的数有 8, 9, 7与 3 性格值最小的为 7此时 ans [8, 8, 7]
第 5 个数为 0前面的数有 8, 9, 7, 3与 0 性格值最小的为 3此时 ans [8, 8, 7, 3]
第 6 个数为 5前面的数有 8, 9, 7, 3, 0与 5 性格值最小的为 3此时 ans [8, 8, 7, 3, 3]
第 7 个数为 11前面的数有 8, 9, 7, 3, 0, 5与 11 性格值最小的为 9此时 ans [8, 8, 7, 3, 3, 9]样例 2:
输入: val[465, 5464, 6467, 6466779, 6461, 56]
输出: [465,5464,6467,6467,465]
解释:
令 ans []
第 2 个数为 5464前面只有第 1 个数 465此时 ans [465]
第 3 个数为 6467前面的数有 465, 5464与 6467 性格值最小的为 5464此时 ans [465, 5464]
第 4 个数为 6466779前面的数有 465, 5464, 6467与 6466779 性格值最小的为 6467此时 ans [465, 5464, 6467]
第 5 个数为 6461前面的数有 465, 5464, 6467, 6466779与 6461 性格值最小的为 6467此时 ans [465, 5464, 6467, 6467]
第 6 个数为 56前面的数有 465, 5464, 6467, 6466779, 6461与 56 性格值最小的为 465此时 ans [465, 5464, 6467, 6467, 465]注意事项
2n100000
0val1000000类似题目LeetCode 315. 计算右侧小于当前元素的个数二叉查找树二分查找归并排序逆序数总结
2. 解题
给一个空数组依次把性格值二分插入到其中检查插入位置前后跟我 绝对值较小 的取为答案变形版 二分查找请参考
class Solution {int l,r,mid;
public:vectorint getAns(vectorint val) {if(val.size() 1)return {};vectorint t;//二分插入数组t.push_back(val[0]);vectorint ans(val.size()-1);int i, idx, k 0, f, b;for(i 1; i val.size(); i,k){idx bs(t,val[i]);//插入位置t.insert(t.begin()idx1,val[i]);//插入数组f (idx 0 ? t[idx] : -10000000);//前面的性格值b (idx2 t.size() ? t[idx2] : -10000000);//后面的性格值if(abs(f-val[i]) abs(b-val[i]))ans[k] t[idx];//取较小的elseans[k] t[idx2];}return ans;}int bs(vectorint a, int target){ //二分查找性格值小于等我的 最后一个l 0, r a.size()-1;while(l r){mid l((r-l)1);if(a[mid] target)r mid-1;else //(a[mid] target){if(mida.size()-1 || a[mid1] target)return mid;elsel mid1;}}return -1;}
};100% 数据通过测试 总耗时 653 ms 您的提交打败了 35.48% 的提交!
