An array is a collection of the same type of data stored on a contiguous memory space
Binary Search
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 + right is out of the range of int, so we have
int mid = left + ((right – left) / 2)
Left-closed and right-closed interval [left, right]
left == right is meaning, so while(left <= right)
Since right is valid index, if(midValue < target) right = mid – 1;
{
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 == right is invalid, so while(left < right)
since right is invalid index, if(midValue < target) right = mid;
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 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.
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>> 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;
}
Dual Pointer Method
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 nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.
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 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.
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 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
