Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
Given target =
5, return true.
Given target =
20, return false.---------------------------------------------------------------------------
REF: http://articles.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html
O(n)
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (matrix[row][col] == target) return true;
if (matrix[row][col] > target) {
col--;
}else {
row++;
}
}
return false;
}
};
O((lgn)^2)
class Solution {
public:
bool helper(vector<vector<int>>& matrix, int target,int rowStart,int rowEnd,int colStart,int colEnd) {
if (rowStart > rowEnd || colStart > colEnd) {
return false;
}
int row = (rowStart + rowEnd) / 2;
int left = colStart,right = colEnd;
while (left <= right) {
int mid = (left + right) / 2;
if (matrix[row][mid] == target) return true;
if (matrix[row][mid] < target) {
left = mid + 1;
}else {
right = mid - 1;
}
}
return helper(matrix,target,rowStart,row - 1,right + 1,colEnd)
|| helper(matrix,target,row + 1,rowEnd,colStart,right);
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
if (m == 0) return false;
int n = matrix[0].size();
return helper(matrix,target,0,m - 1,0,n - 1);
}
};
Majority Number III
Given an array of integers and a number k, the majority number is the number that occurs
more than 1/k of the size of the array.
Find it.
Have you met this question in a real interview?
Yes
Example
Given
[3,1,2,3,2,3,3,4,4,4] and k=3, return 3.
Note
There is only one majority number in the array.
Challenge
-------------------------------------------
O(n) time and O(k) extra space
用hash map来记录value跟count, 原理跟1、2相同
class Solution {
public:
/**
* @param nums: A list of integers
* @param k: As described
* @return: The majority number
*/
int majorityNumber(vector<int> nums, int k) {
// write your code here
unordered_map<int,int> dic;
for (int i = 0; i < nums.size(); i++) {
if (dic.find(nums[i]) == dic.end()) {
dic.insert(make_pair(nums[i],1));
}else {
dic[nums[i]]++;
}
if (dic.size() == k) {
vector<int> t;
for (auto kv : dic) {
t.push_back(kv.first);
}
for (int i : t) {
dic[i]--;
if (dic[i] == 0) {
dic.erase(i);
}
}
}
}
unordered_map<int,int> left;
int maxCount = 0, maxVal = 0;
for (int i = 0; i < nums.size(); i++) {
if (dic.find(nums[i]) != dic.end()) {
if (left.find(nums[i]) == left.end()) {
left[nums[i]] = 1;
}else {
left[nums[i]]++;
}
if (maxCount < left[nums[i]]) {
maxCount = left[nums[i]];
maxVal = nums[i];
}
}
}
return maxVal;
}
};
