一个问题怎么用小程序解决

来源：百度知道 编辑：UC知道 时间：2024/09/26 13:20:59
一个空集合A，有一个系列的整数a1,a2,...an
依次往集合里加数，每加一个数希望记录这个数在当前集合
里有多少个数小于它 用数组b记录 输出b（可以假定ai互不相同）
要求时间是O(nlogn)以内的
输入输出例
n=5 3 5 4 2 1
输出 0 1 1 0 0
希望有个方法 或者直接给个明白一定的程序
先谢过了
虽然我不是很明白matlab 但下面的程序还是能看懂
也许在matlab里集合插入元素和查找元素是O（1）de（我不大相信）
但我感觉用语言C（或类似的C++，java，pascal等）这两个步骤
要在logn类做到不容易
我用二叉树做过 但效率太低 还是会超时
看到一些建议用树状数组之类的完全不懂

^^刚刚再次看了下线段树，会最简单的了，能在nlogn时间内搞定
百度知道有个题
超级平面几何难题求教
https://gss0.baidu.com/7LsWdDW5_xN3otqbppnN2DJv/benkyoshi/pic/item/57065cf1df38bdb6a40f520e.jpg
搞了两天做不出来
帮忙解决下。。。。我有多少分给多少分（不过剩余不多了）

以下是MATLAB程序：
function b=函数名（a) %定义函数
long=length(a); %a数列的长度
A=[]; %定义A是空集
b=[]; %定义b是空集
for i=1:long %i从1开始循环到long
A=[A a(i)]; %往A里加入a数列的元素
wz=find(A<a(i)); %找到A中小于a(i)的元素的“位置”
num=length(wz); %A中小于a(i)的元素的个数
b=[b num]; %把num加入b中
end
输入a=******
再输入b=函数名（a）即可
就算a数列中有重复的元素也适用

这个过程O(n)就可以完成啊,楼上的程序就可以在O(n)时间完成,怎么要求O(nlogn),奇怪中!
ps:应该是O（nlgn）吧
如果强行要求O（nlgn）可以考虑基于排序的方法。
再ps：最初是空数组，因此输出序列应该是
n = 0 0 1 1 0 0