Sort 3 times approach


  • 0
    I

    I do NOT have a proof, but it worked.
    Basically, we sort 3 times as:

    1st sort by number of zeros, and if same, sort by number of cost (cost defined as number of zeros + number of ones needed by a string)

    2nd sort by number of ones, and if same, sort by number of cost (cost defined as number of zeros + number of ones needed by a string)

    3rd sort by cost, and if same, sort depending on Math.min(m, n)

    For each sort, we find the max possible ans. And the final answer is the max of ans1, ans2, ans3

    This approach is not as fast as the DP solution, run time at 80ms. But it deserves sharing I believe :)

    public class Solution {
        public int findMaxForm(String[] strs, int zeros, int ones) {
            if(strs == null || strs.length == 0) return 0;
            
            final int[][] paper = new int[strs.length][2];
            for(int i=0; i<strs.length; i++) {
                final String str = strs[i];
                final int[] temp = new int[2];
                for(int j=0; j<str.length(); j++) {
                    temp[str.charAt(j) - '0']++;
                }
                paper[i] = temp;            
            }
            
            final int Z = zeros, O = ones;
            
            Arrays.sort(paper, (a, b) -> {
                return (a[0] != b[0]) ? a[0]-b[0] : a[0]+a[1]-b[0]-b[1];
            });
            
            int ans0 = 0;
            for(int i=0; i<paper.length && zeros >= 0 && ones >= 0; i++) {
                final int[] temp = paper[i];
                
                if(temp[0] > zeros) break;
                
                if(zeros >= temp[0] && ones >= temp[1]) {
                    ans0++;
                    zeros -= temp[0];
                    ones -= temp[1];
                }
            }
            
            zeros = Z;
            ones = O;
            
            Arrays.sort(paper, (a, b) -> {
                return (a[1] != b[1]) ? a[1]-b[1] : a[0]+a[1]-b[0]-b[1];
            });
            
            int ans1 = 0;
            for(int i=0; i<paper.length && zeros >= 0 && ones >= 0; i++) {
                final int[] temp = paper[i];
                
                if(temp[1] > ones) break;
                
                if(zeros >= temp[0] && ones >= temp[1]) {
                    ans1++;
                    zeros -= temp[0];
                    ones -= temp[1];
                }
            }
    
            zeros = Z;
            ones = O;
    
            Arrays.sort(paper, (a, b) -> {
                if(a[0]+a[1]!=b[0]+b[1]) return a[0]+a[1]-b[0]-b[1];
                else if (Z < O) return a[0] - b[0];
                else return a[1] - b[1];
            });
            
            int ans3 = 0;
            for(int i=0; i<paper.length && zeros >= 0 && ones >= 0; i++) {
                final int[] temp = paper[i];
                
                if(temp[0]+temp[1] > zeros+ones) break;
                
                if(zeros >= temp[0] && ones >= temp[1]) {
                    ans3++;
                    zeros -= temp[0];
                    ones -= temp[1];
                }
            }
            
            return Math.max(ans3, Math.max(ans0, ans1));
        }
    }
    
    

Log in to reply
 

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