数组

一、数组的存储

二维数组在内存的空间地址是连续的吗？

不同编程语言的内存管理是不一样的，在C++中二维数组是连续分布的，但是vector略有不同。

  1. int arr[2][3] = {{0, 1, 2}, {3, 4, 5}};
  2. cout << &arr[0][0] << " " << &arr[0][1] << " " << &arr[0][2] << endl;
  3. cout << &arr[1][0] << " " << &arr[1][1] << " " << &arr[1][2] << endl; 
  5. /**
  6. 0x60fe4c 0x60fe50 0x60fe54
  7. 0x60fe58 0x60fe5c 0x60fe60
  8. **/

可以看到地址是连续的，由于数组是 int类型，所以每个地址间隔 4个字节。

vector略有不同，每个子vector内的存储是连续的，但是子vector之间不是连续的，如下所示：v[0] 和 v[1] 之间有16字节，除去v[0]最后一个元素所占的4字节，可知有12字节的间隔，那么这12字节存储的是什么呢？

vector<vector<int>> vec{{0, 1, 2}, {3, 4, 5}};
cout << &vec[0][0] << " " << &vec[0][1] << " " << &vec[0][2] << endl;
cout << &vec[1][0] << " " << &vec[1][1] << " " << &vec[1][2] << endl; 

/**
0xea1c18 0xea1c1c 0xea1c20
0xea1c30 0xea1c34 0xea1c38
**/

对一个空vector使用sizeof()查看其占用的字节，发现占了12字节：

vector<int> v;
cout<<sizeof(v)<<endl;
/**
输出 12
**/

这是由于vector有三个成员变量，这三个都是原生态指针，占用12字节。

iterator start;  
iterator finish;  
iterator end_of_storage;

二、二分查找

众所周知，二分查找有两种写法：

while( left <= right)：

    条件声明为：`left = 0, right = nums.size() - 1` ，这个边界对于数组来说是**左闭右闭 **的，在循环体内部直接查找元素，把当前搜索区间分为**三部分**，即 **左 、中、 右**，如果等于中间元素，就直接返回，如果大于中间元素，就去右边的区间找，即 **left = mid + 1**；如果小于中间元素，就去左边的区间找，即 **right = mid - 1**。当 **left > right** 时跳出循环，没有找到，**此时 left 在target的插入点下标（也可以说是第一个大于等于target的下标）**，**right 指向 left - 1 位置**。

// leetcode 35.搜索插入位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target) 
                right = mid - 1;
            else 
                return mid;
        }
        return left;
    }
};

while (left < right) ：

    条件声明为：`left = 0, right = nums.size()` ，这个边界对于数组来说是**左闭右开 **的，所以**left == right**时候就没意义了，跳出循环。这种写法表示在循环体内部排除元素，把当前搜索区间分成**两个部分**。一部分是不存目标元素的区间，一部分可能存在目标元素的区间。所以当 `target`大于中间元素，取右边，由于左边是闭的，所以 `num[left]` 肯定不是 `target`值，所以 **left = mid + 1**，当 `target` 小于中间元素，取左边，由于右边是开的，`num[right]` 可能是`target` 值，所以**right = mid**。

    当 **left == right **时没有找到，跳出循环，此时 `left`和 `right` 都在 **target的插入点下标（也可以说是第一个大于等于target的下标）**

// leetcode 35.搜索插入位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;
            else  return mid;
        }
        return left;
    }
};

可将后两个判断合在一起

// leetcode 35.搜索插入位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
};

相关题目：

LeetCode704 - 二分查找

704. 二分查找

简单题，原汁原味的二分查找。

LeetCode35 - 搜索插入位置

35. 搜索插入位置

LeetCode69 - x 的平方根

69. x 的平方根

注意处理边界，注意平方越界

方法一：二分查找后，如果sqrt_x的平方大于x，返回sqrt_x - 1，否则直接返回sqrt_x

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return x;  // 特判，不能使后面的计算除数为0
        int left = 1, right = x, sqrt_x;
        while (left <= right)
        {
            sqrt_x = left + (right - left) / 2;
            if (sqrt_x  < x / sqrt_x)
            {
                left = sqrt_x + 1;
            }
            else if (sqrt_x > x / sqrt_x)
                right = sqrt_x - 1;
            else break;
        }
        return sqrt_x > x / sqrt_x ? sqrt_x - 1 : sqrt_x;
    }
};

方法二：牛顿迭代法

迭代公式： x_{i+1} = \frac{1}{2}(x_i+\frac{C}{x_i})

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        double x_0 = x, C = x, x_1;
        while(1)
        {
            x_1 = 0.5 * (x_0 + C / x_0);
            if (fabs(x_1 - x_0) < 1e-7)
                break;
            x_0 = x_1;
        }
        return (int)x_0;
    }
};

LeetCode367 - 有效的完全平方数

367. 有效的完全平方数

方法一：二分查找

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num < 2) return true; 
        int left = 1, right = num/2;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if ((long long )mid * mid < num)
                left = mid + 1;
            else if ((long long )mid * mid > num )
                right = mid - 1;
            else 
                return true;
        }
        return false;
    }
};

方法二：牛顿法

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num < 2) return true;

        long x = num;
        while (x * x > num)
            x = (x + num / x) / 2;
        return (x * x == num);
    }
};

三、在数组中移除元素问题（首尾双指针，快慢指针）

LeetCode27 - 移除元素

27. 移除元素

方法一：快慢指针

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.size(); ++fast)
        {
            if (nums[fast] != val)
                nums[slow++] = nums[fast];
        }
        return slow;
    }
};

方法二：首尾双指针

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size();
        while (left < right)
        {
            if (nums[left] == val)
            {
                nums[left] = nums[right - 1];
                right--;
            }
            else left++;
        }
        return left;
    }
};