题目

排列组合问题证明
有n个数在输入序列中,其中j个是不相同的.按顺序输出到输出序列,每次输出的时候都和输出序列中的每一个数字比较,如果遇到相同的数字,则把该数字从输出序列中删除,加入到输入序列的末端；如果比较之后,没有相同的数字,则把该数字加入输出序列的末端.请问,最多比较多少次?(N-1)*(N-1)- (J-1)(J-2)/2.请证明.
补充说明:
一开始,
输入序列：1,2,3,3,2,2
输出序列：
比较次数：0
然后输入序列第一个数字,进输出序列.因为输出序列没有元素,所以不需要比较.
输入序列：2,3,3,2,2
输出序列：1
比较次数：0
然后第二个,第三个元素输出
输入序列：3,3,2,2
输出序列：1,2
比较次数：1
输入序列：3,2,2
输出序列：1,2,3
比较次数：3
然后第四个元素3输入,一个个和输出序列的元素进行比较之后,发现有3,则把原来的3从输出序列中删除,加入到输出序列的最后
输入序列：2,2,3
输出序列：1,2
比较次数：6
同样,第五个元素
输入序列：2,3,2
输出序列：1
比较次数：8
第六个元素
输入序列：3,2
输出序列：1,2
比较次数：9
第七个元素
输入序列：2
输出序列：1,2,3
比较次数：11
第八个元素
输入序列：2
输出序列：1,3
比较次数：13
第九个元素
输入序列：
输出序列：1,3,2
比较次数：15

提问时间：2020-06-13

答案