设：                                      

数组定义为A[ , …]

现在查找数组A[ , …]   （其中 对任意n 都存在>）

数组内每个元素的地址大小为 size

 

则其地址为



 

一维数组的地址计算

设每个元素的大小是size，首元素的地址是a[1]，则

a[i] = a[1] + (i-1)*size
若首元素的地址是a[0]

则a[i] = a[0] + i*size
二维数组的地址计算  (m*n的矩阵)

行优先

设每个元素的大小是size，首元素的地址是a[1][1]，则a[i][j]?

分析：a[i][j]位于第i行，第j列。它之前有i-1行，在第i行它之前有j-1个元素。

即a[i][j] = a[1][1] + [n*(i-1) + (j-1)]*size
三维数组的地址计算 (rmn)  r行m列n纵

行优先

首元素的地址a[1,1,1]
a[i,j,k] = a[1,1,1] + [(i-1)*n*m + (j-1)*n + (k-1)]*size
压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，其目的是为了节省存储空间。
二维数组通常用来存储矩阵，特殊矩阵分为两类：

（1）元素分布没有规律的矩阵，按照规律对用的公式实现压缩。

（2）无规律，但非零元素很少的稀疏矩阵，只存储非零元素实现压缩。
一、三角矩阵

包括上三角矩阵，下三角矩阵和对称矩阵

(1)若i<j时，ai,j=0，则称此矩阵为下三角矩阵。

(2)若i>j时，ai,j=0，则称此矩阵为上三角矩阵。

(3)若矩阵中的所有元素满足ai,j=aj,i，则称此矩阵为对称矩阵。

下三角



上三角


二、三对角矩阵



带状矩阵的压缩方法：将非零元素按照行优先存入一维数组。

（1）确定一维数组的存储空间大小：2+(n-2)*3+2 = 3n-2

（2）确定非零元素在一维数组中的地址

loc(i,j) = loc(1,1) + 前i-1行非零元素个数+第i行中ai,j前非零元素的个数

前i-1行：3 * (i-1) - 1，因为第一行只有两个，所以要减去1

第i行中ai,j前非零元素的个数=(j-i)+1,

j-i有三种情况：

（1）j<i   j-i=-1

（2）j==i j-i=0

（3）j>i   j-i=1
loc(i,j) = loc(1,1) + 3(i-1)-1 + j-i+1 = loc(1,1) + 2(i-1) + j-1 = loc(1,1) + 2i+j-3

二维数组名在含义上和一维数组名的含义一样

假如有一个二维数组  ：a[3][2]（从数组名作为右值的角度分析）

则数组名  a  的含义是指二维数组的首元素首地址。这和一维数组名做右值时的含义是一样的。

区别在于，二维数组和一维数组对于内部包含的元素的大小单元的概念是不一样的。
一维数组可以看作是将变量作为数组元素，由多个相同类型的变量顺序排列而组成。

二维数组可以看作是将一维数组作为数组元素，由多个相同长度大小的一维数组顺序排列而成。

所以一维数组以变量作为元素，二维数组以一维数组作为元素。
从而，可以将  a[3][2]  拆成三个一维数组，即  (a[0])[2]  ; (a[1])[2]  ; (a[2])[2];这三个一维数组的数组名，就是用括号括起来的部分，即  a[0]  ;a[1]  ;a[2]  ;
从而，再分析 a 的含义，可以得到的是，a 做右值时，是二维数组中首个一维数组的首地址，也就是二维数组中首个一维数组的地址。
所以可以得到结论就是，二维数组中的数组名作为右值时，它代表的是一个一维数组的地址。所以用来做左值的指针P，必须是一个数组指针！

所以在给指针P赋值时，可以写成P = a；也可以写成P = &a[0];

为什么可以写成P = &a[0]？前面提到过，a[3][2]由(a[0])[2]  ; (a[1])[2]  ; (a[2])[2];这三个一维数组组成，所以二维数组的第一个元素（即能代表整个一维数组的）就是a[0]。对第一个元素a[0]取地址赋予指针P,其意义和P = a；完全相同。
int a[3][2];
int (*p)[2];
p = a;
p = &a[0];//都是取了二维数组第一个元素的地址（只是二维数组的元素是一维数组，取数组的地址需要用数组指针）

那怎么用指向变量的普通指针指向二维数组中的某个值呢？即有用一个 int *p；指针指向a[3][2]中某个变量。
int a[3][2];
int *p;
p = a[0];//p就指向了二维数组的第一个变量
p = &a[0][0];//与上面的语句含义相同

还是同样的道理，始终离不开对数组名的含义的理解。

前面提到过，在a[3][2]中，有三个一维数组(a[0])[2]  ; (a[1])[2]  ; (a[2])[2];这三个一维数组的数组名，就是用括号括起来的部分，即  a[0]  ;a[1]  ;a[2]  ;而数组名的含义是该数组的首元素首地址。

所以这里a[0]做右值，就是向p传递a[0]这个数组的首元素的首地址，由于a[0]是一个一维数组，所以其首元素首地址就是一个int型变量的地址，和int *p；刚好对应。

&a[0][0]的意思也是取一维数组a[0]的首元素的首地址。和a[0]做右值的含义完全相同。
最后，如果想让int *p;指向a[2][1];则书写如下：

p = &a[1][0];

一、剑指Offer 51 数组中的逆序对
  在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
题目地址
示例 1:

输入: [7,5,6,4]
输出: 5

这里的思路主要就是利用了归并的思想，举个例子，对于[1,4,5,7] ,[2,3,6,8]这两个待归并的序列，


  当a[i] > a[j]的时候 显然 [i, m]这个闭区间的所有元素都大于a[j]，此时可以将j为2时候的逆序对全部加入，个数为 m - i + 1，当i > m的时候对于当前的j来说就没有逆序对了。

  还有一种思路是当a[i] <= a[j]的时候，对于i来说[m+1, j - 1]这个闭区间的所有元素都是小于a[i]的，数量为j - m - 1，在 j > r 的时候对于当前i之后位置的每个元素来说都有j - m - 1 也等于r - m个逆序对。这种方式计算的就是对于当前的i，他右边的逆序对的个数，这个思想下一道题会用到。
class Solution {
    int m_count;
public:
    int reversePairs(vector<int>& nums) {
        m_count = 0;
        mergeSort(nums, 0, nums.size() - 1);
        return m_count;
    }
 
    void merge(vector<int>& a, int l, int m, int r) {
        int i = l, j = m + 1;
        vector<int> aux(r - l + 1);
        
        for(int k = 0; k < r - l + 1; k++) {
            if(i > m) {
                aux[k] = a[j++];
            }
            else if(j > r) {
                //m_count += j - m - 1;
                aux[k] = a[i++];
            }
            else if(a[i] <= a[j]) {
                //m_count += j - m - 1;
                aux[k] = a[i++];
            }
            else {
                m_count += (m - i + 1);
                aux[k] = a[j++];
            }
        }
        // while (i <= m && j <= r){
        //     if(a[i] <= a[j]){
        //         aux[k++] = a[i++];
        //     }else {
        //         aux[k++] = a[j++];
        //         m_count = m_count + (m - i + 1);
        //     }
        // }
        // while (i <= m){
        //     aux[k++] = a[i++];
        // }
        // while (j <= r){
        //     aux[k++] = a[j++];
        // }
        ::copy(aux.begin(), aux.end(), a.begin() + l);
    }

    void mergeSort(vector<int>& a, int l, int r) {
        if(l >= r) return;

        int m = l + (r - l) / 2;

        mergeSort(a, l, m);
        mergeSort(a, m + 1, r);

        merge(a, l, m, r);
    }

};

二、LeetCode 315 计算右侧小于当前元素的个数
  给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
题目地址
示例：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

提示：
0 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

  这道题有个比较特殊的地方是要返回原来每个位置元素右边逆序的个数，由于在归并的过程中某个元素的下标会不断改变，那么可以思考这样的思路：将每个元素和他的初始下标用pair关联起来，在交换元素的时候就可可以查看到原始的下标，再根据上题目的第二种思路就可以得到某个元素i右边的逆序数的个数。
class Solution {
    vector<pair<int, int>> m_vpairs;
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size(), l = 0, r = n - 1;
        vector<int> ans(n);
        
        for(int i = 0; i < n; i++){
            m_vpairs.push_back({nums[i], i});
        }

        mergeSort(nums, ans, l, r);
        return ans;
    }

    void merge(vector<int>& ans, int l, int m, int r) {
        int i = l, j = m + 1;
        vector<pair<int, int>> sort_vpairs(r - l + 1);//为了节约时间，每次不必复制整个数组，只需要复制待归并的区间就行

        for(int k = 0; k < r - l + 1; k++){
            if(i > m) {
                sort_vpairs[k] = m_vpairs[j++];
            }
            else if(j > r) {
                ans[m_vpairs[i].second] += j - m - 1;
                sort_vpairs[k] = m_vpairs[i++];
            }
            else if(m_vpairs[i].first <= m_vpairs[j].first) {
                ans[m_vpairs[i].second] += j - m - 1;
                sort_vpairs[k] = m_vpairs[i++];
            }
            else{
                sort_vpairs[k] = m_vpairs[j++];
            }
        }
        ::copy(sort_vpairs.begin(), sort_vpairs.end(), m_vpairs.begin() + l);
    }

    void mergeSort(vector<int>& nums, vector<int>& ans, int l, int r) {
        if(l >= r) return;
        int m = l + (r - l) / 2;

        mergeSort(nums, ans, l, m);
        mergeSort(nums, ans, m + 1, r);

        merge(ans, l, m, r);
    }
};