概述

集合，列表和数组不同点：

  • 集合无顺序，不限制存放类型
  • 列表是有限序列，是由有顺序（线性）的数据项组成，类型不同，长度可变，基于集合形成。表现形式有数组和链表（存储结构）
  • 数组时列表的实现方式之一，它在列表的概念上引入了索引（也叫作数组下标,从0开始），索引就像是图书馆的图书编号一样，可以帮助我们快速找到书籍。数组中的元素在内存中是连续存储的，且每个元素占用相同的内存大小。列表是逻辑层面上的连续，但内存中不一定是连续存储的，因为它还有一种实现方式叫链表（后续会介绍）。

数组的操作

我们来讲解一下数组的4种操作。

读取元素

  • 读取数组中的元素，就是利用数组的索引访问数组中的元素。数组变量一般存储的是第一个数组元素的地址（索引为0），而每个元素都占用相同字节数的内存空间，因此在查找某一个元素的时候，我们只需要将首元素地址加上索引再乘以占用的字节数就可以得出这个元素的内存地址，从而快速获取到这个地址中存放的元素。

  • 元素内存地址计算公式：（首地址+索引）* 一个元素占用字节数。

  • 例如：java中的int数组。假设首地址为2008，读取的索引为3，一个int类型的数据在内存中占用4个字节数。那么读取索引为3的元素的内存地址就为(2008+3) * 4=8044。

  • 这个计算过程非常简单，因此可以将整个访问过程看做是一个动作，时间复杂度为O(1)。

查找元素

以前一直混淆读取元素和查找元素，它们的区别在于：

  • 读取元素：已知索引，返回元素。
  • 查找元素：不知道数组中是否包含这个元素。已知元素，如果包含返回索引

由于在数组中我们只知道索引为0的元素的地址，如果要查找数组中是否包含某个元素，只能从索引0开始，通过与数组中存放的元素逐一比对，直到在找到这个元素或者到达数组末尾后停止搜索。
假设数组中存放了n个元素，最坏的情况是，数组不包含此元素或者此元素在数组末尾，那么需要比较n次，比较一次可视为一次动作，时间复杂度为O(n)。

插入元素
数组插入的元素的效率是很低的。因为一旦插入元素，为了保证数组的连续性，其插入位置之后所有的元素都要往后移动一位。假设数组有n个元素：
最坏情况下是在索引0的位置插入元素，那就意味着整个数组的元素都要往后移动一次，一共要移动n次。时间复杂度为O(n)。
最好情况下是插入索引n的后面，也就是数组最后一个元素的后面，不需要移动任何其他元素，时间复杂度为O(1)。
插入操作最好使用链表结构。
删除元素
删除元素的操作和插入操作几乎一样，只是删除元素后，其元素后面的所有元素都要往前移动一位。
最坏情况下是删除数组的第一个元素，时间复杂度为O(n);
最好情况下是删除数组的最后一个元素，时间复杂度为O(1);

习题

练习题1：寻找数组的中心索引

1.给定一个整数类型的数组 nums，请编写一个能够返回数组 “中心索引” 的方法。
2.我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
3.如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

解答：

/*
这道题最重要的是这句话：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
从数学的角度出发，这里有一个恒等关系：
假设左边的和为leftSum，那么，leftSum + leftSum + nums[centerIndex] = Sum;
假设leftSum为因变量，centerIndex为自变量，那么2*leftSum = Sum - nums[centerIndex];
当等式成立时，返回centerIndex;否则leftSum需要加上nums[centerIndex],centerIndex++进入下一轮的
循环判断;
*/

class Solution {
    public int pivotIndex(int[] nums) {
        int centerIndex = 0;
        int leftSum = 0;
        int sum = 0;

        //计算总和
        for(int i = 0;i<nums.length;i++){
            sum += nums[i];
        }

        while(centerIndex < nums.length){
            if(2*leftSum == sum - nums[centerIndex]){
                return centerIndex;
            }
            leftSum+=nums[centerIndex];
            centerIndex++;
        }

        return -1;
     }
}

练习题2：搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

解答：
本题可以用暴力法和二分法进行解答

/*
暴力法：
由题意已知：当target大于数组末尾的元素，直接返回nums.length；
直接将目标元素和数组元素一一比对，相等，返回该数组元素下标。
如若不相等，判断该数组元素是否大于target，是，返回该数组元素的下标，否，继续判断下一个元素。

最坏情况下，target与数组的倒数第二个元素匹配成功，返回数组下标。假设数组元素有n个，那么需要比较n-1次，时间复杂度为O(n)。
*/
class Solution {
    public int searchInsert(int[] nums, int target) {
        if(target > nums[nums.length-1]){
            return nums.length;
        }
        for(int i = 0;i<nums.length;i++){
            if(target <= nums[i]){
                return i;
            }
        }
       return 0;
    }
}
/*
二分查找法：
本题给出的条件：有序数组，符合二分查找的前提条件。
它的基本思想是：

将给定值target与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；

若是定值target大于中间位置元素，那么target在中间元素到末尾之间

若是定值target小于中间位置元素，那么target在首元素和中间元素之间

再次计算中间元素值，重复上面操作。

当target大于数组的最后一个元素或者小于第一个元素时，数组中不存在target，直接返回末尾下标和首下标就好。

二分法的代码还有另一种写法：
二分法中，包含一个隐含条件，就是当low = mid = high时，若mid != target，则target不在数组中，low=mid+1 > high,循环结束，且此时的low就是target应该插入的位置的下标。
这种写法就是去掉前面两个if语句，然后把48行改成return low;
相对来讲，更推荐第一种二分法代码方式。

二分查找的时间复杂度为O(log(n))
*/
class Solution {
    public int pivotIndex(int[] nums) {
        if(target > nums[nums.length - 1]){
            return nums.length;
        }
        if(target < nums[0]){
            return 0;
        }
        int low = 0;
        int high = nums.length - 1;

        while(low <= high){
            // if(nums[0] > target) return -1;
            if(low <= high){
                int mid = low+(high-low)/2;
                if(target == nums[mid]){

                    return mid;
                }
                else if(target > nums[mid]){
                    low = mid + 1;
                }
                else{
                    high = mid - 1; 
                }
            }
        }

        return 0;

     }
}

未完待续