数据结构，对称矩阵的压缩存储

img


在第1行有1个元素，2有2个元素，那第n行有n个元素，i*( i+1)/2 然后元素ai, j前面有j个元素，答案为什么不是i(i+1)/2＋j呢

不是告诉你从1到n了吗，下标从1开始，那肯定不是i*( i+1)/2而是i*( i-1)/2
你把i=1,j=1代进去就明白了
按你的想法，i*( i+1)/2+j，那么第一行第一列就保存在一维数组下标是2的地方，这对劲吗
如果下标是从0开始那就对了

  • 这篇博客: 《算法导论3rd第九章》中位数和顺序统计学中的 3-4 假设对一个含有n个元素的集合，某算法只用比较来确定第i小的元素。证明：无需另外的比较操作，它也能找到比i小的i-1个元素和比i大的n-i个元素。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

  • 因为在SELECT函数查找第i个元素时，那么就会以这个元素作为主元对整个数组进行划分，低区的i-1个元素肯定都是小于主元的，高区n-i个元素肯定都是大于主元的。