An array is a collection of the same type of data stored on a contiguous memory space
leetcode 704
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
Preventing
left + rightis out of the range of int, so we haveint mid = left + ((right - left) / 2)
Left-closed and right-closed interval [left, right]
-
left == rightis meaning, sowhile(left <= right) - Since
rightis valid index,if(midValue < target) right = mid - 1;
while(left <= right) { int mid = left + ((right -left) >> 1); if(/*equal*/) return mid; else if(/*less*/) left = mid + 1; else // greater right = mid - 1; } return -1;
Left-closed, right-open Interval [left, right)
-
left == rightis invalid, sowhile(left < right) - since
rightis invalid index,if(midValue < target) right = mid;
if(/*equal*/) return mid; else if(/*less*/) left = mid + 1; else // greater right = mid;
Extension Questions
35 Search Insert Position
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
int searchInsert(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while(left <= right) { int mid = left + ((right - left) >> 1); cout << left << right << endl; if(nums[mid] == target) return mid; else if(nums[mid] < target) left = mid + 1; else right = mid - 1; } // now l > r, three situations: // [0, -1] -> 0 // [x, x - 1] -> x // [arraySize, arraySize - 1] return left; }
34 Find First and Last Position of Elements in Sorted Array
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
vector<int> searchRange(vector<int>& nums, int target) { int leftBorder = getBorder(nums, target, true); int rightBorder = getBorder(nums, target, false); if(leftBorder == -2 || rightBorder == -2) return {-1, -1}; if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1}; return {-1, -1};
} /*
* -2 not set
*/ int getBorder(vector<int>& nums, int target, bool bLeftOrRight)
{ int left = 0, right = nums.size() - 1; int border = -2; // not set while(left <= right) { int mid = left + ((right - left) >> 1); // cout << left << right << endl; if(!bLeftOrRight) // calc right border { if(nums[mid] > target) right = mid - 1; else // let left pointer move towards right border, so left move whenever nums[mid] <= target { left = mid + 1; border = left; } } else // calc for left border { if(nums[mid] < target) left = mid + 1; else // let right pointer move towards left border, so right move whenever nums[mid] >= target { right = mid - 1; border = right; } } } return border;
}
59 Spiral Matrix
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
Consider how to divide the intervals
- 4 loops for four sides of a square
- each loop is limited to a left-close right-open interval, the last number letting the next loop handle it.
vector<vector<int>> generateMatrix(int n) { vector<vector<int>> res(n, vector<int>(n, 0)); // 2 dimension array int startx = 0, starty = 0; // start position of each loop int mid = n / 2; // center index int loop = n / 2; // number of loops, if n is odd, extra care at center int count = 1; // number to fill in int offset = 1; // limit the length of row and columns int i,j; while (loop --) { i = startx; j = starty; auto setValueWithLog = [&res, &i, &j, &count]() { res[i][j] = count; cout << "Set(" << i << ", " << j << ") = " << count << endl; ++count; }; // Left-closed (draw), right-open(not draw, next for loop will fill it for us) // left -> right for (; j < n - offset; j++) setValueWithLog(); cout << endl; // up -> down for (; i < n - offset; i++) setValueWithLog(); cout << endl; // right -> left for (; j > starty; j--) setValueWithLog(); cout << endl; // down -> up for (; i > startx; i--) setValueWithLog(); // one loop finished, update the start of next loop ++startx; ++starty; ++offset; } // if n is odd, extra care at the center if (n % 2) { res[mid][mid] = count; } return res;
}
A fast pointer and a slow pointer can do the work of two loops under one loop
Fast and Slow Pointers
27 Remove Element
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:
- Change the array
numssuch that the firstkelements ofnumscontain the elements which are not equal toval. The remaining elements ofnumsare not important as well as the size ofnums. - Return
k.
int removeElement(vector<int>& nums, int val) { int slow = 0; for (int fast = 0; fast < nums.size(); fast++) { if (val != nums[fast]) { nums[slow++] = nums[fast]; } } return slow; } Simulation: f
3 2 2 3 `f++`
s f
3 2 2 3 `nums[f] != 3: nums[s++] = 2; f++`
s f
2 2 2 3 `nums[f] != 3; nums[s++] = 2; f++` s f
2 2 2 3 `f++` s `return 2`
Front and Back Pointers
27 Remove Element
int removeElement(vector<int>& nums, int val) { int left = 0, right = nums.size() - 1; while(left <= right){ if(nums[left] == val){ nums[left] = nums[right]; right--; }else { // 这里兼容了right指针指向的值与val相等的情况 left++; } } return left;
} Simulation: r
3 2 2 3 `nums[0] = nums[3] = 3`
l r
3 2 2 3 `nums[0] = nums[2] = 2`
l r
2 2 2 3
l r
2 2 2 3 `left == right: left++;` l return ++1;
977 Square of sorted non-descending array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
vector<int> sortedSquares(vector<int>& nums) { int l = 0, r = nums.size() - 1; vector<int> res(r + 1); int arrayIndex = r; while(l <= r) { if(abs(nums[l]) >= abs(nums[r])) { res[arrayIndex--] = nums[l] * nums[l]; ++l; } else { res[arrayIndex--] = nums[r] * nums[r]; --r; } } return res;
} Simulation:
1. r
-4 -1 0 3 10 `(-4)^2 < 10^2 : res[i--] = (10^2); r--`
l 2. res: r | i |
-4 -1 0 3 10 | _ _ _ _ 100 |`(-4)^2 > 3^2 : res[i--]=(-4)^2; l++`
l | | 3. res: r | i |
-4 -1 0 3 10 | _ _ _ 16 100 |`(-1)^2 < 3^2 : res[i--]=(3)^2; r--` l | | 4. res r | i |
-4 -1 0 3 10 | _ _ 9 16 100 |`(-1)^2 > 0^2 : res[i--]=(-1)^2; l++` l | | 5. res r | i |
-4 -1 0 3 10 | _ 1 9 16 100 |`(0)^2 > 0^2 : res[i--]=(0)^2; l++` l | | res:
0 1 9 16 100
Sliding Window
The so-called sliding window is a constant adjustment of the starting and ending positions of the subsequence to arrive at the result we want.
209 Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
int minSubArrayLen(int target, vector<int>& nums) { int l = 0, r = 0; int minLen = INT32_MAX; int sum = 0; while(r < nums.size()) { sum += nums[r]; while(l <= r && sum >= target) { if(minLen > (r - l) + 1) minLen = r - l + 1; sum -= nums[l++]; } ++r; } return minLen == INT32_MAX ? 0 : minLen;
} Simulation:
target = 7 r
2 3 1 2 4 3
l r
2 3 1 2 4 3 `sum = 8 > target: minlen = 4;`
l