C++ Solution Beat 93%


  • 0
    C
    class Solution {
    public:
        vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
            vector<int> ret;
            int rows = matrix.size();
            if(rows == 0) return ret;
            int cols = matrix[0].size();
            int total = rows * cols;
            
            bool is_right = false;
            int i = 0, j = 0;
            while(ret.size() != total){
                is_right = !is_right;
                if(is_right){
                    while(i >= 0 && i < rows && j >=0 && j < cols){
                        ret.push_back( matrix[i][j]); i--; j++;  //Go up
                    }
                    // Handle two situation when index out of matrix
                    if(j >= cols){ i+=2; j--; }  //when column, row are both outside matrix 
                    else{ i++; }  //when column is inside matrix just row is outside
                }else{
                    while(i >= 0 && i < rows && j >=0 && j < cols){
                        ret.push_back( matrix[i][j]); i++; j--; //Go down
                    }
                    // Handle two situation when index out of matrix
                    if(i >= rows){ i--; j+=2;}  //when column, row are both outside matrix  
                    else{j++;} //when row is inside matrix just column is outside
                }
            }
            return ret;
        }
    };
    

  • 0
    A

    @CharlesXSH Are you telling the truth? If yes, then LeetCode's perf comparisons are super imprecise. My accepted solution below "beats 52%". I have made a quick perf test of multiple traversals of a matrix close to 10000 elements. My code runs in ~1500ms. Yours in ~4500ms. The code of my test and solution is below.

    class Solution
    {
    	class Iterator
    	{
    		const size_t _rows;
    		const size_t _cols;
    		size_t _r;
    		size_t _c;
    
    	public:
    		Iterator(size_t rows, size_t cols)
    			: _rows(rows)
    			, _cols(cols)
    			, _r(0)
    			, _c(0)
    		{
    		}
    
    		size_t Row() const { return _r; }
    		size_t Col() const { return _c; }
    
    		bool SW()
    		{
    			if (_r + 1 < _rows && _c > 0)
    			{
    				++_r;
    				--_c;
    				return true;
    			}
    			else
    			{
    				return false;
    			}
    		}
    
    		bool NE()
    		{
    			if (_r > 0 && _c + 1 < _cols)
    			{
    				--_r;
    				++_c;
    				return true;
    			}
    			else
    			{
    				return false;
    			}
    		}
    
    		bool NextForNE()
    		{
    			auto r = _r + 1;
    			if (r < _rows)
    			{
    				_r = r;
    				return true;
    			}
    
    			auto c = _c + 1;
    			if (c < _cols)
    			{
    				_c = c;
    				return true;
    			}
    
    			return false;
    		}
    
    		bool NextForSW()
    		{
    			auto c = _c + 1;
    			if (c < _cols)
    			{
    				_c = c;
    				return true;
    			}
    
    			auto r = _r + 1;
    			if (r < _rows)
    			{
    				_r = r;
    				return true;
    			}
    
    			return false;
    		}
    	};
    
    public:
    	vector<int> findDiagonalOrder(const vector<vector<int>>& matrix) const
    	{
    		const size_t rows = matrix.size();
    		if (!rows)
    			return vector<int>();
    		
    		const size_t cols = matrix[0].size();
    		if (!cols)
    			return vector<int>();
    
    		if (rows == 1)
    			return matrix[0];
    
    		if (cols == 1)
    		{
    			auto r = vector<int>(rows);
    			for (size_t i = 0; i < rows; ++i)
    				r[i] = matrix[i][0];
    			return r;
    		}
    
    		auto r = vector<int>(rows * cols);
    		r[0] = matrix[0][0];
    
    		size_t rI = 0;
    		Iterator iter(rows, cols);
    
    		bool movingNE = true;
    		while (true)
    		{
    		if (movingNE)
    		{
    			while (iter.NE())
    				r[++rI] = matrix[iter.Row()][iter.Col()];
    
    			if (!iter.NextForSW())
    				break;
    
    			r[++rI] = matrix[iter.Row()][iter.Col()];
    			movingNE = false;
    		}
    		else
    		{
    			while (iter.SW())
    				r[++rI] = matrix[iter.Row()][iter.Col()];
    
    			if (!iter.NextForNE())
    				break;
    
    			r[++rI] = matrix[iter.Row()][iter.Col()];
    			movingNE = true;
    		}
    		}
    
    		return r;
    	}
    };
    
    // Perf testing
    	vector<vector<int>> big(101);
    	for (size_t _r = 0; _r < big.size(); ++_r)
    		big[_r] = vector<int>(99);
    
    	printf("Prepare\n");
    
    	Solution s;
    	size_t antiAwayOptimizer = 0;
    	for (size_t i = 0; i < 100000; ++i)
    		antiAwayOptimizer += s.findDiagonalOrder(big).size();
    
    	printf("Done. Number is %d\n", int(antiAwayOptimizer));
    
    
    

  • 0
    J

    @andhddn
    It is possible. Your code is longer, which means part of code may not be well cached by Leetcode low-end server CPU. It does not matter if you run a large data set test. BTW, LeetCode perf judgement is always accurate.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.