Day 118, 240 Search a 2D Matrix II, Majority Number III

Search a 2D Matrix II

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;
    }
};