精华内容
下载资源
问答
  • 问题:给定线性序列中 n 个元素和一个整数 k ,1 ≤ k ≤ n,要求找出元素中的第 k 小的元素 或者 第 k 大元素,要求是线性时间算法,即时间复杂度为O( n )。 需要用到快速排序的分区思想,有关分治法思想和快速排序...


    前言

    1. 问题:给定线性序列中 n 个元素和一个整数 k ,1 ≤ k ≤ n,要求找出元素中的第 k 小的元素 或者 第 k 大元素,要求是线性时间算法,即时间复杂度为O( n )。
    2. 需要用到快速排序的分区思想,有关分治法思想和快速排序文章:【算法】分治算法

    分治算法之第k小元素

    1. 问题:给定线性序列中 n 个元素和一个整数 k ,1 ≤ k ≤ n,要求找出元素中的第 k 小的元素 ,要求是线性时间算法,即时间复杂度为O( n )。
    2. 设计思想:
      (1)随机选择序列中第 i 个作为基准元素,统计比基准元素小的元素个数, 如果 个数 比 k 小,说明我们要找的第 k 小元素在基准后半部分,个数比 k 大,说明在前半部分。
      (2)对于无序序列a[s…t],在其中查找第k小元素的过程:
    • 若s=t,即其中只有一个元素,返回a[s]
    • 若s!=t,表示该序列中有两个或两个以上元素,以基准为中心将其划分为a[s…i]和a[i+1…t],a[s…i]中所有元素均小于等于a[i],a[i+1…t]中所有元素均大于a[i]

    j = i-s+1,统计小于等于a[i]的元素个数
    j>=k,第k小元素在a[s…i]中,递归在a[s…i]中寻找第k小元素
    j < k,第k小元素在a[i+1…t]中,递归在a[i+1…t]中寻找第k-j小元素

    在这里插入图片描述

    public class Demo {
    
        public static void main(String[] args) {
            int[] arr={3,1,5,7,8,2,9};
    
            System.out.println(randomizedSelect(arr, 0, arr.length - 1, 4));
        }
    
    
    
        public static int randomizedSelect(int[] a,int s,int t,int k){
            //a[s,t]
            //s == t ==>说明只有一个元素, 输出
            if (s == t){
                return a[s];
            }
    
            //s < t 二个或二个元素以上
    
            //找到基准i 的位置
            int i =  randomizedPartition(a,s,t);
    
            //小于等于 基准的个数
            int j = i - s + 1;
            //k <= j 说明第k小的元素在 前半部分a[s,i]  反之在后半部分a[i+1,t]
            if (j >= k){
                return randomizedSelect(a,s,i,k);
            }else {
                return randomizedSelect(a,i+1,t,k-j);
            }
    
        }
    
    
        //随机产生一个基准的下标===》与第1个元素交换===》分区
        public static int randomizedPartition(int[] a,int p,int q){
            //a[p,q]
            int r = random(p,q);
            swap(a,r,p);
            int i = partition(a, p, q);
            return i;
        }
    
    
        /**
         * 以第一个元素为基准 分区
         * @param a 数组a
         * @param p a[p,q]
         * @param q  a[p,q]
         * @return  分区后基准下标i  a[p,i]和a[i+1,q]
         */
        public static int partition(int[] a,int p,int q){
            int x = a[p];
            int i = p;
    
            for (int j = p; j <= q; j++) {
                if (a[j] < x){
                    i++;
                    swap(a,i,j);
                }
            }
            swap(a,p,i);
            return i;
        }
    
    
        /**
         * 数组交换函数
         * @param a 数组a
         * @param p  下标p
         * @param q   下标q
         */
        public static void swap(int[] a,int p,int q){
            int t = a[p];
            a[p] = a[q];
            a[q] = t;
        }
    
    
        /**
         * 产生一个[p,q]的随机数
         * @param p [p,q]
         * @param q [p,q]
         * @return [p,q]的随机数
         */
        public static int random(int p,int q){
            Random random = new Random();
            return Math.abs(random.nextInt())%(q-p+1) + p;
        }
    
    }
    
    1. 时间复杂度分析

    一个无序数列随机找到一个下标作为基准,每次分区,数列减少一部分,因为每次可以确定第 k 小元素是在基准的前半部分,还是后半部分,如果确定在前半部分,后半部分的数就不需要管了,
    T(n)=T(n/b)+O(n)=O(n)

    分治算法之第k大元素

    在前面那个算法改成比基准大的元素放在前半部分,小的放在后半部分即可。

    public class Demo {
    
        public static void main(String[] args) {
            int[] arr={3,1,5,7,8,2,9};
    
            System.out.println(randomizedSelect(arr, 0, arr.length - 1, 1));
        }
    
    
        public static int randomizedSelect(int[] a,int s,int t,int k){
            //a[s,t]
            //s == t ==>说明只有一个元素, 输出
            if (s == t){
                return a[s];
            }
    
            //s < t 二个或二个元素以上
    
            //找到基准i 的位置
            int i =  randomizedPartition(a,s,t);
    
            //大于等于 基准的个数
            int j = i - s + 1;
            //k <= j 说明第k大的元素在 前半部分a[s,i]  反之在后半部分a[i+1,t]
            if (j >= k){
                return randomizedSelect(a,s,i,k);
            }else {
                return randomizedSelect(a,i+1,t,k-j);
            }
    
        }
    
    
        //随机产生一个基准的下标===》与第1个元素交换===》分区
        public static int randomizedPartition(int[] a,int p,int q){
            //a[p,q]
            int r = random(p,q);
            swap(a,r,p);
            int i = partition(a, p, q);
            return i;
        }
    
    
        /**
         * 以第一个元素为基准 分区
         * @param a 数组a
         * @param p a[p,q]
         * @param q  a[p,q]
         * @return  分区后基准下标i  a[p,i]和a[i+1,q]
         */
        public static int partition(int[] a,int p,int q){
            int x = a[p];
            int i = p;
    
            for (int j = p; j <= q; j++) {
                if (a[j] > x){
                    i++;
                    swap(a,i,j);
                }
            }
            swap(a,p,i);
            return i;
        }
    
    
        /**
         * 数组交换函数
         * @param a 数组a
         * @param p  下标p
         * @param q   下标q
         */
        public static void swap(int[] a,int p,int q){
            int t = a[p];
            a[p] = a[q];
            a[q] = t;
        }
    
    
        /**
         * 产生一个[p,q]的随机数
         * @param p [p,q]
         * @param q [p,q]
         * @return [p,q]的随机数
         */
        public static int random(int p,int q){
            Random random = new Random();
            return Math.abs(random.nextInt())%(q-p+1) + p;
        }
    
    }
    
    展开全文
  • 设计算法,在数组r[n]中删除所有元素值为x的元素,要求时间复杂度为O(n),空间复杂度为O(1)。 1、思路 我们遍历整个原数组,当原数组的值等于x时,我们跳过不进行处理,否则我们将该值记录到新的数组中。这样我们遍历...

    设计算法,在数组r[n]中删除所有元素值为x的元素,要求时间复杂度为O(n),空间复杂度为O(1)。

    1、思路

    我们遍历整个原数组,当原数组的值等于x时,我们跳过不进行处理,否则我们将该值记录到新的数组中。这样我们遍历整个数组的时间复杂度是 O ( n ) O(n) O(n),而删除指定元素的时间复杂度为 O ( 1 ) O(1) O(1)。除去原数组和新数组的空间复杂度为 O ( n ) O(n) O(n),在此过程中,指定元素x的空间复杂度为 O ( 1 ) O(1) O(1)

    核心代码:

    int k = 0; 
    	for(int i = 0; i < n; i++) 
    	{
    		if(a[i] == x)  continue;
    		else 
    		{
    			b[k++] = a[i];
    		}
    	} 
    

    2、测试数据

    第一行输入n,x,分别代表原数组的长度和要删除元素的值,第二行输入原数组的值。

    输出在原数组中删除所有元素值为x的元素后的数组。

    输入:

    10 2
    2 3 4 5 6 7 2 2 9 13
    

    输出:

    3 4 5 6 7 9 13
    

    输入:

    7 5
    4 5 5 6 8 9 5
    

    输出:

    4 6 8 9
    

    3、完整代码

    #include<stdio.h>
    const int N = 10010;
    int a[N]; //原数组
    int b[N]; //记录删除指定元素后的数组 
    int main()
    {
        int n,x;
    	scanf("%d%d",&n,&x);  //输入数组长度和要删除元素的值 
    	for(int i = 0 ; i < n; i++) scanf("%d",&a[i]);
    	int k = 0; 
    	for(int i = 0; i < n; i++) 
    	{
    		if(a[i] == x)  continue;
    		else 
    		{
    			b[k++] = a[i];
    		}
    	} 
    	for(int i = 0; i < k; i++ )  printf("%d ",b[i]);
    	return 0;
    }
    
    展开全文
  • 已知长度为n的线性表A采用顺序存储结构,请写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法可删除线性表中所有值为item的数据元素

    C语言
    运行结果:
    在这里插入图片描述
    代码:

    #include <stdio.h>
    #include <stdlib.h>
    #define OK 1
    #define ERROR -1
    #define MAXSIZE 10
    typedef int Stauts;
    typedef int ElemType;
    typedef struct 
    {
    	ElemType *elem;
    	int length;
    	int listsize;
    }SqList;
    Stauts InitList(SqList &A)
    {
    	A.elem = (ElemType*)malloc(MAXSIZE*sizeof(ElemType));
    	if(!A.elem)  exit(ERROR);
    	A.length = 10;
    	A.listsize = MAXSIZE ;
    	return OK;
    }
    
    Stauts ListDelete(SqList &A,int item)
    {
    	int j=0,i;
    	while(j<A.length)
    	{
    		if(item == A.elem[j])
    		{
    				for(i = j; i < A.length; i++)
    				
    			A.elem[i] = A.elem[i+1];
    		A.length=A.length-1;
    		}
    				
    		j=j+1;
    	}
    	return OK;
    }
    int main()
    {
    	int i;
    	int item ;
    	SqList A;
    	if(InitList(A)) 
    		printf("构建成功\n");
    		printf("当前数据为\n");
    		for(i = 0;i < A.length;i++)
    		{
    			A.elem[i] = i;
    			printf("%6d",A.elem[i]);
    	}
    	printf("\n");
    	printf("请输入要删除的数值");
    	scanf("%d",&item);
    	ListDelete(A,item);
    	
    	printf("删除%d后的数据\n",item);
    	for (i = 0 ;i < A.length; i++)
    		printf("%6d",A.elem[i]);
    	printf("\n");
    	return 0;
    }
    
    展开全文
  • 网页设计排版中哪些元素最重要?

    千次阅读 2017-09-06 18:19:41
    有一些网页设计新手会认为,在设计网页的时候最重要的应该是如何添加一些具有吸引力的内容,所以他们只把大量的精力放在内容的设计上。在我看来,内容质量的好坏确实是能够决定你浏览量多少的关键因素,但事实上,...

    有一些网页设计新手会认为,在设计网页的时候最重要的应该是如何添加一些具有吸引力的内容,所以他们只把大量的精力放在内容的设计上。在我看来,内容质量的好坏确实是能够决定你浏览量多少的关键因素,但事实上,页面的排版也是一门非常大的学问。俗话说“红花还需绿叶衬”,其实我觉得两者之间没有轻重之分,是相得益彰的关系。没有绿叶的陪衬,又怎能显出红花的娇贵呢?一个好的网站设计,不仅要求质量好的内容,还必须有整洁干净的页面排版,才能真正地达到良好的用户体验。

    网页设计排版VS平面设计排版

    网页设计中的排版和平面设计的排版有着很多相似,但又有很多不同。我认为平面设计排版是网页设计排版的基础,在一些文字、图片的排版方面,它们遵循的原则基本是相同的。但是,网页设计排版又会涉及交互性的功能还有动态的效果。所以排版的时候不仅要考虑文字图片等的静态效果,还要考虑一些动态的视觉效果。所以,这么多种元素要呈现在固定大小的页面上,要考虑的情况自然就比平面设计多得多。那么下面我们讨论一下一些在网页设计排版中设计师们注意的一些元素。

    1.文字

    虽然有时候可能一个页面的文字没有几个,但你可千万别小瞧文字的作用。字体的选择,字体的大小、间距以及多种字体如何自然地搭配都是决定你设计的关键因素。在同一个页面有限的文字区域内你所用到的字体样式绝对不止一种,甚至会有三四种,这是为了打破单一字体给用户带来的单调感。字体的搭配是将两种或更多字体通过合理的排版达到最佳效果的过程。对于很多初学者来说,他们觉得选择只用选择漂亮字体就够了,事实上,选择漂亮的字体并不难,如何让它们完美地搭配在一起,相得益彰,这才是应该好好下功夫的地方。



    2.图片

    图片可以说是一个网站的核心了,许多设计师都会把大量的精力放在图片设计上,因为很多用户在浏览网页的时候停留的时间不会太久,更不会花太多时间阅读你的内容。这个时候,一张好看的图片就能够快速有效地抓住用户的眼球。大家所熟知的苹果公司官网大部分都是这样的套路,直接将产品的图片呈现在大家面前,没有过多的赘述,反而会让用户觉得简洁明了。



    3.交互

    交互设计在网页设计中有着相当好的势头,那么在设计交互的时候,必定会涉及到许多的页面、组件。由于这么多的组件元素要排列在同一个页面上,要考虑的情况也就多了许多。在做交互设计之前,你必须站在用户的角度考虑,菜单导航应该在哪个地方最清晰可见?组件应该通过什么样的方式展现用户才会觉得方便?组件和组件之间要怎样排布才会不影响用户的视觉效果?这就要求网页设计师有一个流畅的原型设计过程,通过借助一些原型设计工具(AxureMockplus, Justinmind等)来设计出合理、带来良好用户体验的交互设计。

    4.视频和动画

    如果一个网页只有文字和图片这样静态的元素,难免少了一些生气。现如今,视频和动画的制作成本很低,网络传播性强,与社交媒体网站的兼容性好,甚至在一定程度上,视频和动画传播的有效信息比文本还要多。于是,在网页设计排版中,视频和动画也会被设计师们加入其中。但要注意的是,视频或者和动画设计在同一个版面上不能出现太多,最好一到两处就可以,否则会让用户感到眼花缭乱,甚至它们会喧宾夺主,导致顾客找不到你产品的重点。

    说了这么多理论,我想给大家举三个具有代表性的优秀网页版面设计案例:

    1.Webydo

    Webydo本身就是一个帮助网站设计自由职业者和代理机构的网站,它拥有内置的CMS和托管,可以更快地创建网站并开展业务。我觉得它们的网页设计非常有趣,它们直接将整个页面模拟为我们常见的设计工具页面,明确地传达出了网站主题,也能够准确地吸引目标客户。



    2.CALEO

    CALEO是一部独立的男性出版物,它们的官网页面是很多设计师在实际设计中都会参考的,像这样的时尚网站,大多都会选择用许多图片作为重点,但他们很好地解决如何将它们合理排版,不会造成杂乱的视觉效果,图片之间一定的间距和图片尺寸的大小都有一定的合理规划。



    3.Foreign Policy

    我个人非常中意这个网页设计的原因是它将手绘风格完美地融入了页面设计中,小清新的配色和一目了然的导航菜单排版也是他的亮点之处。此外他们在许多细微的地方都运用了动态效果,让你在浏览时处处都有小惊喜。



    小结:

    所谓最好的设计,就是在整个网页中,你的设计浑然一体,没有突兀的地方,也没有不恰当的结合。成功的排版可以让页面的逻辑性更加明确,让用户产生良好的体验,成功地将用户引导到他们需要的信息上。虽然说设计师最主要的工作是把页面做的漂亮从而创造良好的视觉效果,但是也要关注网页的可操作性。

    展开全文
  • 算法设计思路:因为是顺序表,所以相同的元素一定在连续的位置上。基于此,初始时,将第一个元素看做是非重复的有序表,之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同,若相同则继续向后判断,不...
  • 设计分治法求一个数组中最大元素的位置,建立该算法的递推式并求解。
  • 设计一个支持在平均 时间复杂度 O(1) 下, 执行以下操作的数据结构。 注意: 允许出现重复元素。 insert(val):向集合中插入元素 val。 remove(val):当 val 存在时,从集合中移除一个 val。 getRandom:从现有集合中...
  • 上一篇文章学习了:【算法设计与分析】15 分治策略:芯片测试 文章目录1. 快速排序的基本思想1.2 时间复杂度的计算1.21 最坏情况时间复杂度计算1.22 最好情况时间复杂度1.23 平均时间复杂度计算2 总结 1. 快速排序...
  • *题目:已知长度为n的线性表A采用顺序存储结构,请写一个时间复杂度为o(n)、空间复杂度为o(1)的算法, * 该算法可删除线性表中所有值为item的数据元素。 *编译环境:VC 6.0 */ #include &lt;stdio.h&gt; #...
  • 【算法设计与分析】03 算法及其时间复杂度

    千次阅读 热门讨论 2019-06-29 00:39:02
    输入串的编码长度,通常是数组元素的多少、调度问题的任务个数、图的顶点数与边数等。 算法的基本运算次数可以表示为输入规模的函数。 给定问题和基本运算,就决定了一个算法类 文章目录1 算法的两种时间复杂度1.1...
  • 设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。 insert(val):当元素 val 不存在时,向集合中插入该项。 remove(val):元素 val 存在时,从集合中移除该项。 getRandom:随机返回现有集合中的一...
  • 存储结构: 静态分配 #define MaxSize 30 typedef struct{ ElemType data[MaxSize];...1、从顺序表中删除最小值元素(假设唯一)并由函数返回被删除的元素的值,空出的位置由最后一个元素填补,若...
  • 算法设计与分析 - 主元素

    千次阅读 2013-11-08 10:32:46
    如果T中元素存在序关系,按分治策略设计并实现一个线性时间算法,确定T[0..n-1]是否有一个主元素。 2) 若T中元素不存在序关系,只能测试任意两个元素是否相等,试设计并实现一个O(nlogn)有效算法,确定T是否有一...
  • 设计算法实现在一个具有在n各互不相同元素的数组A[1…n]中找出所有前k个最小元素的问题,这里k不是常量,即它是输入数据的一部分。要求算法的时间复杂性为Θ(n)。 2. 具体要求 输入的第一行是一个正整数m,表示测试...
  • 设计一个算法从A和B中公共元素产生单链表C,要求不破坏A,B的结点。 算法思想: 核心代码: LNode* Public_Element(LNode* &La,LNode* &Lb) { LNode *pa,*pb; pa=La->next; pb=Lb->next; L...
  • 在n个元素的数组中查找第k小的元素。Θ(n)
  • 方法一:用K记录L中不为X的元素的个数,即需要保存的元素的个数,边扫描边统计k,并将不等于X的元素向前移动k个位置,最后修改L长度,K表示不等于X的元素个数。 方法二:用G记录L中等于X的元素的个数,边扫描边统计...
  • 假设你有一个数组,其中第i个元素表示某只股票在第i天的价格。 设计一个算法来寻找最大的利润。你可以完成任意数量的交易(例如,多次购买和出售股票的一股)。但是,你不能同时进行多个交易(即,你必须在再次购买之前...
  • Java常见设计模式总结

    万次阅读 多人点赞 2021-09-18 17:18:54
    设计模式是一套经过反复使用的代码设计经验,目的是为了重用代码、让代码更容易被他人理解、保证代码可靠性。设计模式于己于人于系统都是多赢的,它使得代码编写真正工程化,它是软件工程的基石,如同大厦的一块块...
  • 要求函数min,push,pop的时间复杂度都是O(1). 思路:另外用一个最小栈做辅助结构,记录栈中的最小元素元素栈中保存要入栈的元素。最小栈保存当前的最小元素。 具体过程如下:  1)、入栈时,先入元素栈...
  • 删除顺序表中值相同的多余元素

    万次阅读 多人点赞 2018-06-11 10:11:00
    设计并验证一下算法:设顺序表L中的数据元素为整数且非递增有序,删除其值相同的多余元素,即顺序表L中相同的元素只保留一个,并逆置删除后的顺序表L。(1)根据键盘输入数据建立顺序表L。(2)输出顺序表L、删除值...
  • 元素——答题

    万次阅读 多人点赞 2019-09-19 14:10:44
    元素——答题 微元素每日任务,答题
  • 前端面试题(持续更新中)

    万次阅读 多人点赞 2019-11-06 17:16:33
    伪类用一个冒号来表示,而伪元素则用两个冒号来表示。 伪元素选择器:dom中不存在的元素,仅仅是css中用来渲染,添加一些特殊效果的,比如p::before,选择p标签(真元素)前面的假元素(伪元素,p标签前面没有元素...
  • 时间轮(TimeWheel)的设计与实现

    千次阅读 2018-08-22 22:11:39
     由于工作的需要,得实现一个用于控制事件超时抛弃的时间轮,由于这是一个相对独立的接口,就总结分享一下。  首先看下需求,此时间轮需要具备下面几个功能:  1)能添加事件,同时附上其超时时间;  2)如果...
  • 设计一个支持在平均时间复杂度 O(1)下,执行以下操作的数据结构。 insert(val):当元素 val 不存在时,向集合中插入该项。 remove(val):元素 val 存在时,从集合中移除该项。 getRandom:随机返回现有集合中的一...
  • //存储空间的基地址 , 用“elemtype”代表所有可能的数据类型,简单明了的概括了整体。在算法中,除特别说明外,规定ElemType的默认是int型。 int length ; //当前长度 } SqList ; //sqlist代表上面的结构体...
  • 注意: 总时间限制: 1000ms 内存限制: 65536kB 描述 输入一个整数矩阵,计算位于矩阵边缘的元素之和。所谓矩阵边缘的元素,就是第一行和最后一行的元素以及第一列和最后一列的元素。 输入 第一行为整数k,表示有k...
  • 设顺序表a中的数据元素递增有序,试设计一个算法,将x插入到顺序表的适当位置,以保持该表的有序性。
  • 我们现在来看一个最坏情况运行时间为O(n)O(n)O(n)的选择算法。像randomized_select(arr, low, high, i)一样, 下文所述的选择算法通过对输入数组的递归划分来找出所需元素,但是,在该算法中能够保证得到对数组的一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 354,615
精华内容 141,846
关键字:

代表时间的设计元素