基础类型题 oj 篇3

深藏阁楼爱情的钟 2023-06-19 14:25 63阅读 0赞

### 基础类型题 oj 篇3 ###

*   *   *  2、寻找峰值
         *  7.求众数
         *  8.最大间距
         *  10.阶乘后的零

### 2、寻找峰值 ###

峰值元素是指其值大于左右相邻值的元素

给定一个输入数组 nums，其中 nums\[i\] ≠ nums\[i+1\]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums\[-1\] = nums\[n\] = -∞

**说明:你的解法应该是 O(logN) 时间复杂度的**

> 示例1  
> 输入: nums = \[1,2,3,1\]  
> 输出: 2  
> 解释: 3 是峰值元素，你的函数应该返回其索引 2。

> 示例2  
> 输入: nums = \[1,2,1,3,5,6,4\]  
> 输出: 1 或 5  
> 解释: 你的函数可以返回索引 1，其峰值元素为 2；  
> 或者返回索引 5， 其峰值元素为 6。

思路一：O(n) 的时间复杂度进行遍历

思路二：二分查找，我们知道二分查找是用于有序数据，但是这些数据完全都是无序的呀，而且不可能排序，排序就无法正确返回峰值下标。

那是因为我们之前二分查找是中间数据和左(右)边数据比较的，这次我们用 mid 和 mid + 1 比较

def findPeakElement(nums) :
            left,right = 0,len(nums)-1
            while left<right:
                mid = (left+right)//2
                # 如果右边大于左边说明还没到达峰值
                if nums[mid]<nums[mid+1]:
                    left = mid+1
                else:
                    right = mid
            return left

### 7.求众数 ###

给定一个大小为 n 的数组，找到其中的众数。**众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素**

你可以假设数组是非空的，并且给定的数组总是存在众数。

> 示例1  
> 输入: \[3,2,3\]  
> 输出: 3

> 示例2  
> 输入: \[2,2,1,1,1,2,2\]  
> 输出: 2

思路一：排序后取出中间的数据

思路二：借助字典进行计数的方式来判断众数，空间复杂度为O(N)

def majorityElement(self, nums: List[int]) -> int:
            dic = { }
            if len(nums)==1:
                return nums[0]
            for i in range(len(nums)):
                if nums[i] not in dic:
                    dic[nums[i]] = 1
                else:
                    dic[nums[i]]+=1
                    if dic[nums[i]]>len(nums)//2:
                        return nums[i]

思路三：通过计数的方式，先用一个变量保存第一个值，并计数为1，如果下一个值和变量值相等，则计数 +1，如果不相等则计数 -1，如果计数 等于 0 的时候，把下一个值赋值给该变量，最后返回变量的值，它一定是众数

**核心思想就是将众数和不是众数的次数抵消了，然后最后一个数一定是众数了**

参考代码

def majorityElement(self, nums: List[int]) -> int:
            n = len(nums)
            ans = nums[0]
            time = 1 # 次数
            for i in range(1,n):
                if time == 0:
                    ans = nums[i]
                if ans == nums[i]:
                    time+=1
                else:
                    time-=1
            return ans

### 8.最大间距 ###

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值

如果数组元素个数小于 2，则返回 0

> 示例1  
> 输入: \[3,6,9,1\]  
> 输出: 3  
> 解释: 排序后的数组是 \[1,3,6,9\], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

> 示例2  
> 输入: \[10\]  
> 输出: 0  
> 解释: 数组元素个数小于 2，因此返回 0。

思路一：排序后进行判断

def maximumGap(self, nums: List[int]) -> int:
            if not nums or len(nums)<2:
                return 0
            nums.sort()
            max_num = 0
            n = len(nums)
            for i in range(1,n):
                max_num = max(nums[i]-nums[i-1],max_num)
            return max_num

思路二：桶排序的原理

### 10.阶乘后的零 ###

给定一个整数 n，返回 n! 结果尾数中零的数量。

> 示例1  
> 输入: 3  
> 输出: 0  
> 解释: 3! = 6, 尾数中没有零。

> 示例1  
> 输入: 5  
> 输出: 1  
> 解释: 5! = 120, 尾数中有 1 个零.

只有5\*2可以得到0

只要有偶数就能分解出2，2的个数一定比5多，所以只用计算5的个数  
对于20来说，只有5，10，15，20包含5，故20!结尾有20/5=4个零

当然不止这么简单，对于25来说：只有5，10，15，20，25，包含5，结尾却有6个零，因为25=5x5，包含两个5

所以 **f(n)=n/5+f(n/5)**

def trailingZeroes(self, n: int) -> int:
            if n<5:
                return 0
            if n<10:
                return 1
            return int(n/5) + self.trailingZeroes(int(n/5))