81:搜索旋转数组2

  1. class Solution {
  2. public:
  3.     bool search(vector<int> &nums, int target) {
  4.         int n = nums.size();
  5.         if (n == 0) {
  6.             return false;
  7.         }
  8.         if (n == 1) {
  9.             return nums[0] == target;
  10.         }
  11.         int l = 0, r = n - 1;
  12.         while (l <= r) {
  13.             int mid = (l + r) / 2;
  14.             if (nums[mid] == target) {
  15.                 return true;
  16.             }
  17.             if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
  18.                 ++l;
  19.                 --r;
  20.             } else if (nums[l] <= nums[mid]) {
  21.                 if (nums[l] <= target && target < nums[mid]) {
  22.                     r = mid - 1;
  23.                 } else {
  24.                     l = mid + 1;
  25.                 }
  26.             } else {
  27.                 if (nums[mid] < target && target <= nums[n - 1]) {
  28.                     l = mid + 1;
  29.                 } else {
  30.                     r = mid - 1;
  31.                 }
  32.             }
  33.         }
  34.         return false;
  35.     }
  36. };

88:合并两个有序数组

  • 解法1：直接将数组2插入到数组1后面，然后对合并后的数组进行排序

    class Solution {
public:
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
      for(int i=0;i<n;i++) {
          nums1[m+i] = nums2[i];
      }
      sort(nums1.begin(),nums1.end());
  }
};

  • 解法二：双指针

    class Solution {
public:
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
      int p1 = 0, p2 = 0;
      int sorted[m + n]; //用于保留合并后的数组 空间复杂度 O(m+n)
      int cur;
      while (p1 < m || p2 < n) {
          if (p1 == m) {
              cur = nums2[p2++];
          } else if (p2 == n) {
              cur = nums1[p1++];
          } else if (nums1[p1] < nums2[p2]) {
              cur = nums1[p1++];
          } else {
              cur = nums2[p2++];
          }
          sorted[p1 + p2 - 1] = cur;
      }
      for (int i = 0; i != m + n; ++i) {
          nums1[i] = sorted[i];
      }
  }
};

  • 解法3：逆向双指针

对于解法2，从头往后遍历数组的话，如果不用额外的数组，有些元素可能被覆盖，因为元素初始有序，且数组空间够大，可以使用逆向双指针，从后往前比较两个数组中较大者，放到nums1的后面，这样可以将nums1剩余的空间利用起来，不需要额外空间，空间复杂度为O(1)

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }
};

645:错误的集合

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++)
        {
            while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i])
            {
                /* nums[i] != i + 1代表元素位置不对
                nums[nums[i] - 1] != nums[i] 不是被替换的元素，
                如果位置不对并且被其他元素替换了，就不用管它
                每次 while 索引i处的值都会在正确的位置

                如果输入是 [1,2,2,4]这种，这个循环没什么吊用
                如果输入是[2,2,4,1]这种位置不对的，这个循环会把数组变为[1,2,2,4]
                */
                swap_index(nums, i, nums[i] - 1);
            }
        }

        for (int i = 0; i < nums.size(); i++)
        {
            //找到被覆盖的元素，那么重复的元素就是nums[i]，被覆盖的就是 i+1
            if (nums[i] != i + 1)
                return vector<int>{nums[i], i + 1};
        }

        return vector<int>{};
    }
    void swap_index(vector<int> &nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

数组[1, 2, 2, 4]
索引 0, 1, 2, 3
i=0和i=1时,发现 nums[i] = i+1,也就是位置正确 while里的条件是false
i=2时，发现nums[i] != i+1，也就是说位置不对，
那么这个元素本来应该放的位置处的索引是index = 数值(nums[i]) - 1,因为正确的位置数值都会比索引大1
但是找到应在的位置，发现nums[index]处的值和nums[i]一样,也就是说这个元素有可能是被nums[nums[i] - 1]替换的,所以位置依然是“正确的”，所以while中的条件 nums[nums[i] - 1] != nums[i] 仍然是false
数组[2, 2, 4, 1]
索引 0, 1, 2, 3
nums[0] 不等于1，但是 nums[2-1]=nums[1]=nums[0]=2，所以暂时认为1被2替换，然后nums[1]等于2，跳过
//while
nums[2] 不等于 3并且nums[4-1]不等于4, 交换 nums[2]和nums[3]，数组变为[2, 2, 1, 4]，交换完发现nums[2]还是不等于3，并且nums[1-1]不等于1，接着交换，数组变为[1,2,2,4],
然后所有元素都在正确的位置了

1588:所有奇数长度子数组的和

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int n = arr.size();
        int res = 0;
        for (int i = 0; i < n; i++) { // i代表连续子数组的起始点
            for (int j = 1; i + j - 1 < n; j += 2) {// j是当前子数组的结束的位置 开区间
                res += accumulate(arr.begin() + i, arr.begin() + i + j, 0);
                //accumulate的本质就是在计算从 arr[i] 到 arr[i + j - 1] 的连续子数组的和
            }
        }
        return res;
    }
};