Algorithms: Array
Published:
41. First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
找到第一个缺失的正整数，每个正整数放在n-1的下标上。
int firstMissingPositive(vector<int>& nums) {
for (int i = 0; i < nums.size();) {
if (nums[i] != nums[nums[i] - 1] && nums[i] - 1 >= 0 && nums[i] - 1 < nums.size()) {
swap(nums[i], nums[nums[i]-1]);
} else {
i++;
}
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != i + 1) return i+1;
}
return nums.size()+1;
}
73. Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
click to show follow up.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
Subscribe to see which companies asked this question.
Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
将矩阵中出现0的行和列全部设置为0。主要是空间复杂度上O(m+n) => O(1)不好想，不遍历第一列，使用col0记录第一列是否出现0.
void setZeroes(vector<vector<int> > &matrix) {
int col0 = 1, m = matrix.size(), n = matrix[0].size();
for (int i = 0; i < m; ++i) {
if (!matrix[i][0]) col0 = 0;
for (int j = 1; j < n; ++j) {
if (!matrix[i][j]) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 1; --j) {
if (!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
}
if (!col0) matrix[i][0] = 0;
}
}
485. Max Consecutive Ones
解析: 找出0,1数组中 连续1出现的最长个数。
边界：为空
思路：可以使用left、right指针，很好写。更简单易懂的方式是使用计数器len，遍历数组在数组元素为1时，len++，数组元素为0时，len=0
时间复杂度：O(n)
int findMaxConsecutiveOnes(vector<int>& nums) {
int max_cnt = 0, cnt = 0;
for (auto n : nums) {
if (n == 1) max_cnt = max(++cnt, max_cnt);
else cnt = 0;
}
return max_cnt;
}
448. Find All Numbers Disappeared in an Array
解析: 找出数组中未出现的数字(1<= nums[i] <= n)
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
边界：
思路：可以使用笨方法，空间复杂度O(n)。也可以使用trick，将出现的下标的元素+= n。
时间复杂度：O(n)
vector<int> findDisappearedNumbers(vector<int>& nums) {
for (auto n:nums) {
nums[(n-1)%nums.size()] += nums.size();
}
vector<int> ret;
for (int i = 0; i< nums.size(); ++i) {
if (nums[i] <= nums.size()) {
ret.push_back(i+1);
}
}
return ret;
}
238. Product of Array Except Self
解析: 求数组中其他元素的乘积，不允许除法，要求O(n) 时间，O(1)空间
Input: [1,2,3,4]
Output: [24,12,8,6]
边界：数组为空
思路：这道题不好想，因为不允许除法。使用左右乘积，left每次记录乘到上一个的积，right每次记录从后往前乘积。当left和right有交叉时，便形成了所有左边的乘积乘以右边的乘积。关键点：left、right累积乘积，res数组初始化为1，从而res[i]*left*right的结果为去除该元素外的乘积。
时间复杂度：O(n)
vector<int> productExceptSelf(vector<int>& nums) {
int left = 1, right = 1;
vector<int> res(nums.size(),1);
for (int i = 0; i < nums.size(); ++i) {
res[i] *= left;
left *= nums[i];
res[nums.size() - 1 -i] *= right;
right *= nums[nums.size() -1 - i];
}
return res;
}
531. Lonely Pixel I
解析: 求行列中只有B的点的个数
边界：数组为空
思路：分别记录行、列的B出现次数，再进行一次循环元素为’B’且行、列出现次数都为1时，为不重复点。
时间复杂度：O(nm)
int findLonelyPixel(vector<vector<char>>& picture) {
vector<int> rows(picture.size(),0);
vector<int> columns(picture[0].size(),0);
for (int i = 0; i < picture.size(); ++i) {
for (int j = 0; j < picture[i].size(); ++j) {
if (picture[i][j] == 'B') {
rows[i]++;
columns[j]++;
}
}
}
int res = 0;
for (int i = 0; i < picture.size(); ++i) {
for (int j = 0; j < picture[i].size(); ++j) {
if (picture[i][j] == 'B' && rows[i] == 1 && columns[j] == 1) {
res++;
}
}
}
return res;
}
289. Game of Life
According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.” Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article): Any live cell with fewer than two live neighbors dies, as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population.. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Write a function to compute the next state (after one update) of the board given its current state. Follow up: Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
解析: 矩阵每个点附近8个位置
live -> live 2/3
dead -> live 3
其他情况都为dead。
思路：1. 遍历全部位置的附近位置，判断满足下一阶段为live的情况，board[i][j] |= 2。 2. 遍历全部位置board[i][j] 右移一位
void gameOfLife(vector<vector<int>>& board) {
int m = board.size(), n = m?board[0].size():0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int count = 0;
for (int I = max(i - 1, 0); I < min (i + 2, m); ++I) {
for (int J = max(j - 1, 0); J < min(j + 2, n); ++J) {
count += board[I][J] & 1;
}
}
if (count == 3 || count - board[i][j] == 3) {
board[i][j] |= 2;
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
board[i][j] >>= 1;
}
}
}
57. Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
解析: 插入间隔到不重叠的间隔数组中
边界：数组为空，不重叠
思路：题目挺简单，但是思路要清楚简洁。1. 插入前面不重叠的部分。 2. 找出重叠部分最小的起始位置和最大的结束位置，插入新的间隔。 3. 插入后面不重叠的部分
时间复杂度：O(n)
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> res;
auto it = intervals.begin();
for (; it != intervals.end(); ++it) {
if (newInterval.start > it->end) res.push_back(*it);
else if (newInterval.end < it->start) break;
else {
newInterval.start = min(newInterval.start, it->start);
newInterval.end = max(newInterval.end, it -> end);
}
}
res.push_back(Interval(newInterval.start, newInterval.end));
res.insert(res.end(), it, intervals.end());
return res;
}
127. Word Ladder
解析: 起始词到达终止词最短距离
边界：数组为空
思路：BFS。此处使用的技巧是双向BFS，2头都可以找能到达且存在于给定词典中的，每次使用短的那个进行遍历。startWords为某一段能到达的集合，比endWords短。
时间复杂度：O(n!)
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
if (dict.find(endWord) == dict.end()) return 0;
unordered_set<string> startWords({beginWord});
unordered_set<string> endWords({ endWord });
return ladderHelper(startWords, endWords, dict, 1);
}
int ladderHelper(unordered_set<string> startWords, unordered_set<string> endWords, unordered_set<string> dict, int level) {
if (startWords.empty()) return 0;
if (startWords.size() > endWords.size()) return ladderHelper(endWords, startWords, dict, level);
for (auto word : startWords) dict.erase(word);
for (auto word : endWords) dict.erase(word);
unordered_set<string> middleWords;
for (auto word : startWords) {
string newWord = word;
for (int i = 0; i < word.size(); ++i) {
word = newWord;
for (int j = 0; j < 26; j++) {
word[i] = 'a' + j;
if (endWords.find(word) != endWords.end()) return level + 1;
else if (dict.find(word) != dict.end()) {
middleWords.insert(word);
}
}
}
}
return ladderHelper(middleWords, endWords, dict, level + 1);
}