精华内容
下载资源
问答
  • 在未排序的数组中找到第 k 最大的元素, 示例 : 输入: nums = [3, 2, 1, 5, 5, 6, 4] 和 k = 3 输出: 5 解法一:先排序取值 常规做法是先对数组nums从大到小排序,然后nums[k-1]就行。 排序算法可以选择快速...

    题目描述

    在未排序的数组中找到第 k 个最大的元素,

    示例 :
    输入: nums = [3, 2, 1, 5, 5, 6, 4] 和 k = 3
    输出: 5

    解法一:先排序后取值

    常规做法是先对数组nums从大到小排序,然后取nums[k-1]就行。
    排序算法可以选择快速排序,或者使用Python内置函数sorted(),此解法较简单,就不赘述了。时间复杂度是O(NlogN),N是nums长度。

    解法二:堆

    使用Python的heapq小顶堆求解。
    时间复杂度O(Nlogk) N是nums长度。

    def solution(nums: list) -> int:
        # 初始化一个空列表,用于创建堆
        heap = []
        for i, n in enumerate(nums):
            if i < k:   # 先往堆中push k个元素
                heapq.heappush(heap, n)
            else:
                # 从第 k + 1个元素开始,每次和堆顶(最小值)比较,如果比堆顶大,就移除堆顶,同时把n推入堆中
                # heapreplace作用其实是先pop堆顶 然后再push
                if heap[0] < n:
                    heapq.heapreplace(heap, n)
        return heap[0]
    

    解法三:快速选择法

    此方法和快速排序类似。

    class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            # 选择枢轴
            pivot = len(nums) // 2
            tmp = nums[pivot]
            nums.remove(tmp)
            # 定义两个数组,left存放大于枢轴的数字,right存放小于枢轴的数字
            left = []
            right = []
            for n in nums:
                # 大于枢轴的放左边
                if n > tmp:
                    left.append(n)
                # 小于等于枢轴的放右边
                else:
                    right.append(n)
            # 如果左边的列表长度刚好等于 k - 1,那么第k大元素就是枢轴
            if len(left) == k - 1:
                return tmp
            # 如果左边的列表长度大于k-1,说明第k大的元素在左边的列表,继续对left递归求解
            elif len(left) > k - 1:
                return self.findKthLargest(left, k)
            # 如果左边的列表长度小于k-1,说明第k大的元素在右边的列表,继续对left递归求解,注意此时对右边求的是第(k - len(left) - 1)大的元素
            else:
                return self.findKthLargest(right, k - len(left) - 1)
    
    
    展开全文
  • 请注意,你需要找数组排序后的第 k 最大的元素,而不是第 k 不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明: 你可以假设 k 总是...

    在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

    示例 1:

    输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5
    示例 2:

    输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4
    说明:

    你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

     这一题可能是高频考题吧!涉及到快速排序和堆排序。

    针对本题,第一想法:先从大到小排序,然后取第K个值。我掌握最熟练的冒泡排序,但是它的时间复杂度太高了,为O(n^2),运行完了提示时间超出了限制。

    解法一:快速排序

    思想:分而治之。设立一个基准值pivot,通过一趟排序后,大于pivot的放在右边,小于pivot的数放在左边。对左右两边分别递归排序,直至整个数组排好序。时间复杂度O(nlogn),空间复杂度O(logn)(递归使用栈的空间代价)

    class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            def quicksort(arr,l,r):
                if l>=r:
                    return arr
                pivot = arr[l]
                low = l
                high = r
                while(l<r):
                    while(l<r and arr[r]>=pivot):
                        r = r-1
                    arr[l] = arr[r]
                    while(l<r and arr[l]<=pivot):
                        l = l+1
                    arr[r] = arr[l]
                arr[l] = pivot
                quicksort(arr,low,l-1)
                quicksort(arr,l+1,high)
            quicksort(nums,0,len(nums)-1)
            return nums[len(nums)-k]

     

     解法二:快速选择排序

    在快速排序的基础上,可以进一步改进为快速选择排序。即判断较大值排序好的序列长度是否为K,如果为K,直接返回;如果小于K,则继续对左子序进行排序;如果大于K,则对右子序进行排序即可。

    class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            low,high = 0,len(nums)-1
            def quicksort(arr,l,r):
                if l>=r:
                    return l
                pivot = arr[l]
                low = l
                high = r
                while(l<r):
                    while(l<r and arr[r]>=pivot):
                        r = r-1
                    arr[l] = arr[r]
                    while(l<r and arr[l]<=pivot):
                        l = l+1
                    arr[r] = arr[l]
                arr[l] = pivot
                return l
            
    
            while True:
                l = quicksort(nums,low,high)
                if len(nums)-l == k:
                    return nums[l]
                elif len(nums)-l<k:
                    high = l-1
                else:
                    low = l+1

    解法三:堆排序

    对于一个堆(Heap)来说,1.完全二叉树2.所有父节点都大于(或小于)子节点。一定要从上到下,从左到右依次添加。

    分为大顶堆(升序排列)(父节点大于两个子节点)和小顶堆 (降序排列)。平均时间复杂度O(nlogn)。空间复杂度是O(logn)。

    对于一个完全二叉树,节点标号为i,那么父节点标号为(i-1)/2,向下取整;左子节点标号为2i+1,右子节点为2i+2

    从最后一个节点的父节点开始heapify,首先将整个二叉树进行堆化,然后交换根节点和最后一个节点,取出最后一个节点,对新的二叉树进行堆化。

    有个博主视频讲解堆排序很清晰:https://www.bilibili.com/video/BV1Eb41147dK/?spm_id_from=333.788.recommend_more_video.-1

    class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            def swap(arr,i,j):
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
    
            def heapify(arr,n,i):
                c1 = 2*i+1
                c2 = 2*i+2
                max = i
                if c1<n and arr[c1]>arr[max]:
                    max = c1
                if c2<n and arr[c2]>arr[max]:
                    max = c2
                if i!=max:
                    swap(arr,i,max)
                    heapify(arr,n,max)
    
            def build_heap(arr,n):
                last_node = n-1
                parent = int((last_node-1)/2)
                for i in range(parent,-1,-1):
                    heapify(arr,n,i)
            
            def heap_sort(arr,n):
                build_heap(arr,n)
                for i in range(n-1,-1,-1):
                    swap(arr,i,0)
                    heapify(arr,i,0)
            
            heap_sort(nums,len(nums))
            return nums[len(nums)-k]

     

    展开全文
  • L[0:3],L[:3] 截取前3个元素。 L[1:3] 从1开始截取2个元素出来。 L[-1] 倒数第一个元素出来。 L[-10] 取后10个数 L[10:20] 前11-20个数 L[:10:2] 前10个数,每两个一个 L[::5] 所有数,每5个一个 L[:] ...
  • 今天看MDNet中看见,samples[:, 2:] *= self.aspect ** ratio不是很明白samples[:, 2:]是如何取值。写了几个python语句大致是明白了...a[:,2:] *=2#第一维全部,第二维从下标为2开始到最后,然后让这些元素

    今天看MDNet中看见,samples[:, 2:] *= self.aspect ** ratio不是很明白samples[:, 2:]是如何取值的。写了几个python语句大致是明白了。

    逗号前面代表第一维,逗号后面代表第二维。冒号前面是起始位置,冒号后面是结束位置

    1.a[:,2:]

    a = np.array([1,2,3,4])
    a = np.tile(a,(5,1))
    print("原数组\n",a)
    a[:,2:] *=2#第一维全部取,第二维从下标为2的开始取,取到最后,然后让这些元素自身乘以2 
    print("变换后的数组\n",a)
    
    '''
    原数组
     [[1 2 3 4]
     [1 2 3 4]
     [1 2 3 4]
     [1 2 3 4]
     [1 2 3 4]]
    变换后的数组
     [[1 2 6 8]
     [1 2 6 8]
     [1 2 6 8]
     [1 2 6 8]
     [1 2 6 8]]
    '''

    2.a[:,0:2] 

    a = np.array([1,2,3,4])
    a = np.tile(a,(5,1))
    print("原数组\n",a)
    a[:,0:2] *=2#第一维全部取,第二维从第0列开始选,选到第二列,然后让其乘以2,这个语句等价a[:,:2] 
    print("变换后的数组\n",a)
    
    '''
    原数组
     [[1 2 3 4]
     [1 2 3 4]
     [1 2 3 4]
     [1 2 3 4]
     [1 2 3 4]]
    变换后的数组
     [[2 4 3 4]
     [2 4 3 4]
     [2 4 3 4]
     [2 4 3 4]
     [2 4 3 4]]
    '''

    3.a[1:3,:] 

    a = np.array([1,2,3,4])
    a = np.tile(a,(5,1))
    print("原数组\n",a)
    a[1:3,:] *=2#第一维选取1,2行,第二维全部选。让其乘以2
    print("变换后的数组\n",a)
    
    '''
    原数组
     [[1 2 3 4]
     [1 2 3 4]
     [1 2 3 4]
     [1 2 3 4]
     [1 2 3 4]]
    变换后的数组
     [[1 2 3 4]
     [2 4 6 8]
     [2 4 6 8]
     [1 2 3 4]
     [1 2 3 4]]
    '''

     

    展开全文
  • 求一无序数组的中位数(Python

    千次阅读 2018-11-08 19:31:08
    最简单方法是先将数组排序,然后找中位数。但此种方法肯定不是最优。一个比较好做法是利用小顶堆。思路如下: 1.前len(nums)//2个元素...3.数组剩下所有元素比较完,可以输出中位数。数组长度为奇数时...

    最简单的方法是先将数组排序,然后找中位数。但此种方法肯定不是最优的。一个比较好的做法是利用小顶堆。思路如下:

    1.取前len(nums)//2个元素建立小顶堆。可以知道堆顶元素是前len(nums)/2个元素中最小的。

    2.从第len(nums)//2+1个元素开始,依次将其与堆顶元素比较。若比对顶元素大,则替换之,并调整堆。

    3.数组剩下的所有元素比较完后,可以输出中位数。数组长度为奇数时,输出堆顶元素即可。数组长度为偶数时,输出堆顶元素与它的孩子结点中较小的那个的均值。

    代码如下:

    #coding:utf-8
     
    def heap_adjust(parent,heap):   #更新结点后进行调整
        child=2*parent+1
        while len(heap)>child:
            if child+1<len(heap):
                if heap[child+1]<heap[child]:
                    child+=1
            if heap[parent]<=heap[child]:
                break
            heap[parent],heap[child]=heap[child],heap[parent]
            parent,child=child,child*2+1
     
    def find(nums):
        heapnum=len(nums)//2
        heap=nums[:heapnum+1]
        for i in range(len(heap)//2-1,-1,-1):   #前n/2个元素建堆
            heap_adjust(i,heap)
        for j in range(heapnum+1,len(nums)):
            if nums[j]>heap[0]:
                heap[0]=nums[j]
                heap_adjust(0,heap)
        #奇数时是最中间的数,偶数时是最中间两数的均值
        return heap[0] if len(nums)%2==1 else float(heap[0]+min(heap[1],heap[2]))/2
    

     

    展开全文
  • 同样的看成一维数组的话,一行就是一个元素。 执行a[:, ::-1],上下前后交换。相当于对行逆序,对列逆序。 a=np.arange(12).reshape(3,4) a array([[ 0, 1, 2, 3], [ 4, 5, 6, 7], [ 8, 9, 10, 11]]) a...
  • 求无序数组的中位数

    千次阅读 2018-10-02 21:35:01
    求无序数组的中位数,我们首先想到的是将该数组进行排序,然后找到中间的元素,但是往往面试的时候,面试官就会怼你,说你时间复杂度太高了....要你优化(个人感觉,面试官对你问了问题,有一自己的标准,如果你答...
  • Python 插入排序

    2020-04-29 16:12:16
    一、逻辑 1.取数组的第一个元素为已经排序...3.取数组的第三个元素,依次和第一个第二个元素进行比较,排序完成第一个,第二个,第三个元素形成一个有序数列 4.重复取第四个元素,第五个元素,第六个元素...... ...
  • 以50000随机元素的列表为例: 暴力法需要约两分钟,分治法需要0.19s,而动态规划只需要0.013s。(单次数据) import math import time import random def force(profit): """ use forceful meth...
  • 给定一非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。...3数组的最大值,删掉。再一次(第二大),删掉。此时数组中的最大值即为第三大的值 cl...
  • 插入排序核心:通过构建有序序列,对于...下一个元素,对已排序数组往前扫描 若从排序数组中取出元素大于新元素,则移至下一位置 重复步骤3,直至找到已排序元素小于或等于新元素位置 插入新元素至该位置...
  • 【问题描述】每次都是优化选出一个元素(分组后的中位数)为划分基准,在线性时间内寻找第i小元素。提示:分组时个数为n/5向下取整;分组后的中位数第(num_group/2向上取整)小元素。 【输入形式】在...
  • python学习笔记

    2020-12-22 18:43:04
    L[0:3],L[:3] 截取前3个元素。 L[1:3] 从1开始截取2个元素出来。 L[-1] 倒数第一个元素出来。 L[-10] 取后10个数 L[10:20] 前11-20个数 L[:10:2] 前10个数,每两个一个 L[::5] 所有数,每5个一个 L[:] ...
  • Python实现快速排序

    2020-08-12 20:00:26
    将大于或等于分界值的数据放到数组右边,小于分界值的数据放到数组的左边,此时左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值; 然后,左边和右边的数据都可以独立排序。对于左侧的...
  • 1、可变列表list,使用...这个函数是1-10之间数为一个数组。 1)、增加: 增加一个元素:name.append(&amp;quot;a&amp;quot;) #在列表后面追加一个元素 name.extend(strlist) #将一个列表strlist内元...
  • python-List 与 tuple

    2020-09-27 22:58:55
    1.List 与 tuple Python内置一种数据类型是列表:list。list是一种有序集合,可以随时添加和删除其中的元素。 比如,列出班里所有同学名字...1 可以从往前-1, -2, -3取 2 元素类型可以不同 3 由pop append i
  • ##快速排序算法 ...## step1: 取数组第一个元素为key值,设置两个变量,i = 0, j = len(a) - 1 ## step2: j从后面开始遍历,遇到小于key值,则a[i] = a[j] ## step3: i从前面开始遍历,遇到大于key值,则a[j]
  • print(a[-1]) ###最后一个元素 print(a[:-1]) ### 除了最后一个全部 print(a[::-1]) ### 向前(逆序)元素 print(a[2::-1]) ### 从下标为2元素翻转读取 [0 1 2 3 4] 4 [0 1 2 3] [4 3 2 1 0] [2
  • // 打印出3,因为该是数组3个元素 // 用一个语句定义一个数组并赋值 $myphonebook = array ( "sbabu" => "5348", "keith" => "4829", "carole" => "4533" ); // 噢,忘了教长吧,让我们添加一个元素 $myphonebook...
  • 但是需要注意是,在常规归并排序时候,如果前一个元素大于后一个元素,直接进行交换即可,只进行了一次操作,但是对于这道题来讲,对于每一次归并段,我们选择从向前遍历,前面归并段某一个数值left[i]...
  • 第28~37行用于绘制检测到直线,其中lines[i][0]~lines[i][3]中存储个元素分别为第i条直线端点1X,Y坐标和端点2X,Y坐标。 第38行中变量[draw_arrow],是函数drawSegments参数之一,默认值为false,用于...

空空如也

空空如也

1 2
收藏数 36
精华内容 14
关键字:

python取数组的后3个元素

python 订阅