Share my Java solution O(n) < O(m), Why?


  • 0
    C

    O(m)

    public class Solution {
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
            int m = 0;
            while(n!=0){
                n&= n - 1;
                m++;
            }
            return m;
        }
    }
    

    Above code segment costs 233ms, while following code costs 288ms!

    O(n)

    public class Solution {
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
            int m = 0;
    	    for(int i=0;i<32;i++)
    	    	if((n&(1<<i))!=0)
    	    		m++;
    	    return m;
        }
    }
    

    I think preceding one is better, but actually not, why?


  • 0
    W

    I have been thinking that while() is faster than for.
    And your second solution has 32 times run, the first may be less


  • 0
    R

    public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
    int m = 0;
    while(n!=0){
    n&= n - 1;
    m++;
    }
    return m;
    }
    }


Log in to reply
 

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