精华内容
下载资源
问答
  • 问题描述:在数组中找到 k 大的元素。要求时间复杂度为O(n),空间复杂度为O(1) 分析:此类问题为排序问题,主要难点在于时间复杂度为O(n),采用快速排序算法进行排序 function quickSort(nums,k,start,end){ if...

    问题描述:在数组中找到第 k 大的元素。要求时间复杂度为O(n),空间复杂度为O(1)
    分析:此类问题为排序问题,主要难点在于时间复杂度为O(n),采用快速排序算法进行排序

    function quickSort(nums,k,start,end){
    	if(start>=end){
    		return nums[k];
    	}
    	var left=start,right=end;
    	var key=nums[Math.floor((start+end)/2)];
    	while(left<=right){
    		while(left<=right&&nums[left]<key){
    			left++;
    		}
    		while(left<=right&&nums[right]>key){
    			right--;
    		}
    		if(left<=right){
    			swap(nums,left,right)
    			left++;
    			right--;
    		}
    	}
    
    	if(k<=right){
    		return quickSort(nums,k,start,right)
    	}
    	if(k>=left){
    		return quickSort(nums,k,left,end)
    	}
    	return nums[k];
    	
    }
    
    function swap(nums,i,j) {
            var tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
    }
    

    1、基数的选择影响时间复杂度,O(选最左边的为基数)>O(选最中间的数为基数),一般来说当块划分的相对平均的时候时间复杂度较低
    2、js中/得出的结果为实际值,如果要取整需要使用相应的函数如(parseInt丢弃小数部分,保留整数,floor向下取整,round四舍五入,ceil向上取整)

    展开全文
  • 这几天在看浙江大学陈越的那本数据结构这本书,看到二章里有一个求书有求集合中第K大数的问题。按照它的思路,我想来试一试。 思路:用一个基准数e,将集合S分解为两个不包含e在内的两个集合S1和S2,其中S1...

    这几天在看浙江大学陈越的那本数据结构这本书,看到第二章里有一个求书中有求集合中第K大数的问题。按照它的思路,我想来试一试。

    思路:用一个基准数e,将集合S分解为两个不包含e在内的两个小集合S1和S2,其中S1中任何元素均大于等于e,S2中任何元素均小于e。记S1长度为len,如果len>=K,则说明第K大数在S1中,如果len=K-1,那么e是第K大数,否则第K大数在S2中,并且是第K-len-1大数。

    这是教材中的思路。但是我的做法与这个有一些不同。

    首先我先解释一下,为啥在S2中是求K-len-1大数:
    为什么比基数小的数组里是求第 K-len(比基数大的数组)-1    
    在比基数小的数组中,要找的数在里面第几大数变了,减去比 k大的集合的数量,再减去基数。
    

    按照这个思路:

    1. 首先要将数组分成两个比基准数大和小的两个集合,可以运用快速排序算法的思想。
      如果想了解快速排序算法,可以看我的博客中有快速排序算法
    2. 然后就是按照返回的比基准数大集合的大小与K值作比较,重新设立递归条件。

    代码:

    基准总取数组最左边这个数,注意不是第0个数。
    将大于等于的基准数的数放原数组前面,返回的right,就是大于等于的基准数数组的大小。
    

    注意:我这里于教材思路不同的地方在于,不是将数组划分成了两个数组,还是在一个数组中,当第K大值在比基准数小的数组中时,还是求第K个数的大小,不是第K-len-1个数的大小。

    #include<stdio.h>
    #include<Windows.h>
    #pragma warning(disable:4996)
    //按快速排序算法求数组最大K值
    int Swap(int arr[], int left, int right){//将比基准数大的数放前面,将比基准数小的数放后面
    	int temp = arr[left];
    	while (left < right){
    		while (temp >= arr[right] && left < right){
    			right--;
    		}
    		arr[left] = arr[right];
    		while (temp <= arr[left] && left < right){
    			left++;
    		}
    		arr[right] = arr[left];
    	}
    	arr[right] = temp;//基准数放中间
    	return right;
    }
    
    static int Findklargest(int a[], int left,int right, int k){
    	int temp = Swap(a, left, right);//返回的是比基数大的数组的大小
    	if (temp >= k)
    		return Findklargest(a, left, temp - 1, k);//第k个值在大数数组这边
    	else if (temp < k - 1)
    		return Findklargest(a, temp + 1, right, k);//第k个数在小数数组这边,还是求第k个数的大小
    	else
    		return a[temp];
    	return -1}
    
    int main(){
    	int a[] = { 5, 1, 2, 3, 8, 7, 6, 9, 5, 4, 3 };
    	int num = sizeof(a) / sizeof(a[0]);
    	int k = 0;
    	scanf("%d", &k);
    	int result = Findklargest(a, 0, num - 1, k);
    	printf("%d\n", result);
    	system("pause");
    	return 0;
    }
    
    展开全文
  • 下面用倍增法求后缀数组,每次计算从i开始,长度为k的字符串的字典序rank(i,k)利用基数排序的思想,我们已经计算好了rank(i,k),然后我们在rank(i,k)的基础上,rank(i+k,2k)进行排序,得到的排序结果就是rank(i,2k)的...

    我们只要记录字符串每个后缀的起始位置,就可以表示字符串的每一个后缀。将这种表示按照后缀的字典序排序,就得到了后缀数组。下面用倍增法求后缀数组,每次计算从i开始,长度为k的字符串的字典序rank(i,k)利用基数排序的思想,我们已经计算好了rank(i,k),然后我们在rank(i,k)的基础上,rank(i+k,2k)进行排序,得到的排序结果就是rank(i,2k)的结果。下面代码给出了O(n*log^2 n)的复杂度实现,如果排序算法使用基数排序,可以将复杂度降到O(n*log n)

    int n, k;
    int rank[maxn];
    int tmp[maxn];
    
    bool compare(int i, int j) {
        if(rank[i] != rank[j]) return rank[i] < rank[j];
        else {
            int ri = i + k <= n ? rank[i + k] : -1;
            int rj = j + k <= n ? rank[j + k] : -1;
            return ri < rj;
        }
    }
    
    void calc_sa(char *s, int *sa) {
        n = strlen(s);
        //初始长度为1时
        for (int i = 0; i <= n; i++) {
            sa[i] = i;这样赋值,当用rank对sa进行排序后,sa的值就表示排名第i的后缀是谁
            rank[i] = i < n ? s[i] : -1;//将每个字符的编码赋值给rank
        }
        for (k = 1; k <= n; k *= 2) {
            std::sort(sa, sa + n + 1, compare);
            //用新排序的sa和rank生成新的rank,存在tmp里,然后再赋值给rank
            tmp[sa[0]] = 0;
            for (int i = 1; i <= n; i++) {
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare(sa[i - 1], sa[i]) ? 1 : 0);
            }
            for (int i = 0; i <= n; i++) {
                rank[i] = tmp[i];
            }
        }
    }
    展开全文
  • 在未排序的数组中找到 k 个最大的元素。请注意,你需要找的是数组排序后的 k 个最大的元素,而不是 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 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 ≤ 数组的长度。

    思路1:基于快排的partition思想(从大往小排)

    • 选定一个数作为基点,将小于基点数点放在左边,大于等于基数的放在右边。
    • 确定查找区域:如果左边的个数小于k,则说明第k大的数在基数右边区域。否则,则说明在左边区域。
    • 在查找区域利用partition直接找到序号为k-1的数。
    //返回基数在序列的位置
        int partition(vector<int>&nums,int left,int right)
        {
            int key=nums[right];
            for(int i=left;i<right;i++)
            {
                if(nums[i]<key)
                    swap(nums[left++],nums[i]);
                swap(nums[right],nums[left]);
                return left;
            }
    
        }
        int findKthLargest(vector<int>& nums, int k) {
            int len=nums.size(),order_k=len-k,pos,left=0,right=len-1;
            while((pos=partition(nums,left,right))!=order_k)
            {
                pos<order_k ? left=pos+1 : right=pos-1;
            }
            return nums[order_k];
        }
    

    思路2:基于堆排序的思想。

    • 用前k个数建立最小堆,然后从 k+1个数开始,与堆顶比较,如果大,就交换,直到结束。
    • 堆里存放大数组前k个最大大元素,堆顶为第k大元素
     void HeapAdjust(vector<int>& nums,int s,int length)//调整堆的程序
        {
            int temp=nums[s];
            int child = 2*s+1;//这里因为下标从0开始,每个节点的子节点就是2s+1
            while(child<length)
            {
                if(child+1<length && nums[child]>nums[child+1])
                    child++;
                if(nums[s]>nums[child])
                {
                    nums[s]=nums[child];
                    s=child;
                    child=2*s+1;
                }
                else
                    break;
                nums[s]=temp;//这里的s已经是原来的child了
            }
        }
        void BuildingHeap(vector<int>& nums,int k)//建立堆,从最后开始筛选
        {
            for(int i=(k-1)/2;i>=0;i--)
                HeapAdjust(nums,i,k);
        }
    
    int findKthLargest(vector<int>& nums, int k)
        {
            int size=nums.size();
            if(k>size) return nums[size-1];
            vector<int> mynum;//(nums.begin(),nums.begin()+k);
            int index=0;
            for(;index<k;index++)
            {
                mynum.push_back(nums[index]);
            }
    
            int j=index;
            for(int i=j;i<size;i++)
            {
                if(nums[i]>mynum[0])
                {
                    swap(nums[i],mynum[0]);
                    HeapAdjust(mynum,0,index);
                }
            }
            return mynum[0];
        }
    
    展开全文
  • 在面试碰到求数组中第K小的数,(或者最小的的K个数)。 最直观的方法是排序之后,选择数组A的元素A[K-1]; 以快速排序为例,排序的时间复杂度为O(NlogN), 选择元素的时间为O(1)。 如果允许使用额外空间,则...
  • 所谓“(前)k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到顺序的(前)k个数的问题。  转自(http://www.cppblog.com/superKiki/archive/2011/04/10/143858.html) 解法1:我们可以对这个乱序...
  • 返回数组中第n大的数

    2020-03-28 15:07:37
    给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。 示例 输入: [3, 2, 1] 输出: 1 解释: 三大的数是 1 输入[1, 2] 输出:2 解释:三大的数不存在,...
  • 在一个int数组中,寻找最大的k个数字,时间复杂度是O(n)。 数组不大情况下 思路: 类似于基本排序基数排序,利用空间换时间,待排序数组的值是新数组的索引,新数组的值就是出现的次数,考虑重复的情况 新...
  • ,就扫描一遍数组,得到数组中最小的数 Y 。用 X 替代 Y ,或者保持原数组不变。这样的方法,所耗费的时间为 O ( N  *  K )。 进一步,可以用容量为 K 的最小堆来存储最大的 K 个数。最小堆的堆顶元素就是...
  • Subarray Sum Equals K(找出数组中连续子串和等于k) 文章目录: 题目描述: 题目分析: 1)暴力算法: 2)优化算法(堆排序): 3)最优算法(快速排序) 源码地址: 题目描述: 输入整数数组 arr ,找出其中最小的...
  • 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。 class Solution: def ...
  • 第K小/大的数(树状数组解法)

    千次阅读 2013-09-25 23:05:50
    第K小/大数这个题目...或者是构建一个顶堆,遍历数组取最小的K个数,再然后还有所谓的快速选择,有人证明了可以在O(n)时间内解决,不过我不太清楚这种算法是否对重复元素有效(但看了代码其实就是快排的一种应
  • 一、数组中的逆序对: 1、题目: 数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%...
  • 给定一个无序的整数数组,怎么找到一个大于0,并且不在此数组的整数。比如[1,2,0]返回3,[3,4,-1,1]返回2,[1, 5, 3, 4, 2]返回6,[100, 3, 2, 1, 6,8, 5]返回4。要求使用O(1)空间和O(n)时间。   这道题目初看...
  • 注:不懂基数排序的看...落谷P3809【模板】后缀数组 C++代码实现: #include &lt;bits/stdc++.h&gt; using namespace std; #define infy 0x3f3f3f3f #define lowbit(x) (x&amp;(-x)) #define e ex...
  • Fortran分配数组大小

    千次阅读 2019-03-04 19:43:33
    用Fortran写程序经常会分配一些数组使用,但究竟能分配多大的数组,这受编译环境、电脑可用内存容量、数组分配方式的影响,做了些测试,分享一下。 操作系统:Win8.1 64位 内存:8G(由于集成显卡需要使用一部分...
  • (1)y[]数组表示按照二关键字排号的情况,目前里面存的时一关键字的值,比如 y[1]=4,表示二关键字排在1位上此时一关键字为下标从4开始的子字符串。因此用基数排序,因为其相当稳定。 (2)swap交换后...
  • 基于数组基数排序

    2012-11-15 22:01:15
    实现了一个基于数组基数排序工具类,备用。public class ArrayBasedRadixSort { //M是基数, 数字的每一位为0..M-1 private int M = 0; //EXP[i]=M^i; private int[] EXP = null; //初始化 public ...
  • 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。 思路:先找出奇数数组,再找...
  • 位数:数组长度是基数,则位数是中间值;数组长度是偶数,则位数是中间两个数的算术平均值 例如:nums1 = [1, 3], nums2 = [2], 则位数是2;nums1 = [1, 2], nums2 = [3, 4], 则位数是(2+3)/2 = 2.5.
  • 数组

    2020-01-04 22:00:49
    数组 一维数组 一维数组声明方式 int[] ii; 一维数组初始化 动态初始化:数组声明且为数组元素分配空间与赋值操作分开进行 int[] arr = new int[3]; //声明一个能存放4个int类型数据的数组 arr[0] ...
  • 基数排序-数组模拟实现

    千次阅读 2014-12-22 13:48:59
    之前用队列实现了基数排序,后来我想了想,结合桶排的思路,计数排序的思路,我觉得根本不需要队列,用队列太麻烦了,结合别人的代码部分,加上自己的理解,在这里讲解一下:数组是如何模拟基数排序的分配和收集过程...
  • 一步,首先将所有的位置上的值装入数组中,并记录排名为i的数为sa[i],i个数的排名为rank[i]. 下面就要进行logn次的倍增操作,我们定义k为当前倍增长度 基数排序,痛苦ing 首先将每一对数的排名存到cur数组,...
  • 后缀数组及其辅助数组模板、
  • 首先找出数组中的最大元素确定最高位数,然后根据有效位数排序直到最高位数,排序即完成。 步骤: #include<iostream> void LsdSort(int a[],int length); //使用lsd——基数比较法给数组排序
  • 1.题目 数组中重复的数字 2.描述 在一个长度为n的数组里的所有数字都在0到n-1的范围内。... 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是一个重复的数字2。 3.解题思路 python实现 ...
  • 后缀数组·

    千次阅读 2014-08-08 14:51:37
    花了将近20天总算是把后缀数组论文
  • 后缀数组小

    2016-07-29 15:47:31
    后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也并不逊色,而且它比后缀树所占用的内存空间很多。可以说,后缀数组比后缀树要更为实用。自从拜读了罗穗...
  • LSD的基数排序适用于位数的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”建立“子桶”,将每个...
  • 二维数组[][]:数组中数组2. 二维数组内存解析四、数组中常见算法1. 二分查找法2. 排序算法1)排序算法分类:内部排序和外部排序。2) 十大内部排序算法3) 算法5大特征4) 排序实质:5)各种内部排序方法性能...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,406
精华内容 10,962
关键字:

数组中第k小的基数