面试之leetcode分治-求众数，x幂等

1 leetcode50 计算 x 的 n 次幂函数。

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

(1)调用库函数

(2)暴力o(N)

(3)分治

xxxxxx.......x 采用两端夹,如果是偶数 y=x的二分之n次方 result=y*y。如果是奇数，x的二分之n次方，result=y*y*x

x(n)->x(n/2)->x(n/4).....x(0) 每次减半，logn

 class Solution(object):

     def myPow(self, x, n):

         """

         :type x: float

         :type n: int

         :rtype: float

         """

         if not n:

             return

         if n<:

             return  / self.myPow(x,-n)

         if n%:

             return x*self.myPow(x,n-)

         return self.myPow(x*x,n/)

非递归

 class Solution(object):

     def myPow(self, x, n):

         """

         :type x: float

         :type n: int

         :rtype: float

         if not n:

             return

         if n<:

             return  / self.myPow(x,-n)

         if n%:

             return x*self.myPow(x,n-)

         return self.myPow(x*x,n/)

         """

         if n<:

             x=/x

             n=-n

         pow=

         while n:

             if n&:

                 pow*=x

             x*=x

             n>>=

         return pow

2 leetcode169 求众数

(1)暴力两个循环，针对每一个x进行计数,时间复杂度n平方

(2)map，key为元素，value为count

c++版本时间复杂度0(n) 循环一次每一次对mapO(1)

 class Solution {

 public:

     int majorityElement(vector<int>& nums) {

         unordered_map<int,int>hash;

         int res=;

         int len=nums.size();

         for(int i=;i<len;i++)

         {

             hash[nums[i]]++;

             if(hash[nums[i]]>len/)

             {

                 res=nums[i];

             }

         }

         return res;

     }

 };

(3) sort nlogn

(4)分治

先分两部分，left和right，如果right==left，那么总体也是ok，结果就是right/left。如果不相等，比较谁count大

 def majorityElement(self, nums):

     if not nums:

         return None

     if len(nums) == :

         return nums[]

     a = self.majorityElement(nums[:len(nums)//2])

     b = self.majorityElement(nums[len(nums)//2:])

     if a == b:

         return a

     return [b, a][nums.count(a) > len(nums)//2]

巴特西

面试之leetcode分治-求众数，x幂等

最新文章

热门文章