精华内容
下载资源
问答
  • 1.二分查找输入查找值,返回查找值的数组下标(查找的数组arr,数组的开头start,数组的结尾end,查找的值key) 先判断输入的start(开头)是否比end(结尾)大,如果比end(结尾)大返回-1; 2.在以上的大范围之下...

    1.冒泡排序

    对无序数组进行排序方法,参数为无序数组,return有序数组。
    外部的for循环是对每一个值进行内部的for循环,
    内部for循环是把最大值放到数组的最后一个

    public static int[] mao(int[] arr){
    		for(int j=0;j<arr.length;j++) {
    		//
    			  for(int i = 0;i<arr.length-1;i++) { 
    				  if(arr[i]>arr[i+1]) {   
    				      int da=arr[i];
    					  int xiao=arr[i+1];
    					  arr[i]=xiao;
    			          arr[i+1]=da; 
    			  }else { 
    				  continue; 
    				  } 
    			   } 
    			}
    		return arr;
    	}
    

    2.递归方法实现二分查找法

    1.二分查找输入查找值,返回查找值的数组下标(查找的数组arr,数组的开头start,数组的结尾end,查找的值key)
    先判断输入的start(开头)是否比end(结尾)大,如果比end(结尾)大返回-1;
    2.在以上的大范围之下,最先的是对arr[mid](开头的值和结尾的值与中间数组的值)进行判断,如果和key(查找的值)的数组一样,返回mid(该中间数组的下标值),结束
    3.如果以上不成立,再判断arr[mid](中间数组的值)是不是小于需要查找的值,如果小于,则说明key(查找的值)在数组右边,那么给mid附值给一个新的开始值newstart,然后递归,start的值改变为newstart
    4.如果以上也不成立,那么就只剩下arr[mid]>key,则说明key(查找的值)在数组左边,给mid附值给一个新的结束值newend,然后递归,end的值改变为newend

    public int erfenchazhao(int[] arr,int start,int end,int key) {
    		if(start>end) {
            //如果输入的数组开头比结尾大那么直接结束,返回负一
    			return -1;
    		}else {
    			int mid = (end-start)/2;
                //新建中间值mid
    			if(arr[mid]==key) 
                //中间值和查找值一样
                {
    				return mid;
    			}else if(arr[mid]<key)
                //中间值比查找值小,查找值在它右边,舍弃数组左边,中间值变成新的开始值,递归直到查找和中间相等返回中间值mid。
                {
    				int newstart = mid;
    				return erfenchazhao(arr,newstart,end,key);
    			}else 
                //中间值比查找值大,查找值在它左边,舍弃数组右边,中间值变成新的结束值,递归直到查找和中间相等返回中间值mid。
                {
    				int newend =mid;
    				return erfenchazhao(arr,start,newend,key);
    			}
    		}
    	}
    

    3主方法测试

    public static void main(String[] args) {
    		int arr[]= {6,9,2,10,18,27,48,1,44};
    		maopao m=new maopao();
    		int houarr[]=m.mao(arr);
    		
    		  for(int i:houarr) System.out.print(i+" ");
    		  //排序后,输出有序数组
    		  System.out.println();
    		  
    		  Test1 test1=new Test1();
    		 System.out.println(test1.erfenchazhao(houarr, 0, houarr.length-1, 10));
    		 //输出查找值的下标值
    	}
    

    最终结果:查找10返回数组值为10的下标值。
    在这里插入图片描述

    展开全文
  • 题目:有一个无序整型数组,如何求出该数组排序后的任意两个相邻元素的最大差值? 解法一:直接快排然后求差值 时间复杂度O(nlogn),空间复杂度O(n) 使用任意一种时间复杂度为O(nlogn)的排序算法(如快排)给原...

     

     

    两个相邻元素的最大差值

    题目:有一个无序整型数组,如何求出该数组排序后的任意两个相邻元素的最大差值?

    解法一:直接快排然后求差值

    时间复杂度O(nlogn),空间复杂度O(n)

    使用任意一种时间复杂度为O(nlogn)的排序算法(如快排)给原数组排序,然后遍历排好序的数组,并对每两个相邻元素求差,最终得到最大差值。

    解法二:计数排序的思想利用数组下标求解

    步骤:

    1. 利用计数排序的思想,先求出原数组的最大值max和最小值min的区间长度k(k = max - min + 1) ,以及偏移量d = min
    2. 创建一个长度为k的新数组Array
    3. 遍历原数组,每遍历一个元素,就把新数组Array对应下标的值 + 1 。例如原数组元素的值为n,则将Array[n - min]的值加1.遍历结束后,Array的一部分元素值变成了1或更高的数值,一部分元素值仍然是0。
    4. 遍历新数组Array,统计出Array中最大连续出现0值得次数 + 1,即为相邻元素最大差值

    解法三:桶排序的思想

    1. 利用桶排序的思想,根据原数组的长度7,创建出个桶,每一个桶代表 个区间范围。其中第1个桶从原数组的最小值mn开始,区间跨度是(max-mn)/(n-1)。

    2. 遍历原数组,把原数组每一个元素插入到对应的桶中,记录每一个桶的最大和最小值。

    3. 遍历所有的桶,统计出每一个桶的最大值, 和这个桶右侧非空桶的最小值的差,数值最大的差即为原数组排序后的相邻最大差值。

    package some_problem;/**
     * Copyright (C), 2019-2020
     * author  candy_chen
     * date   2020/7/20 21:22
     * version 1.0
     * Description: 求出一个无序数组排序后的任意两个相邻元素的最大差值
     */
    
    /**
     *
     */
    public class GetMaxSortedDistance {
        
        /**
         * 桶
         */
        private static class Bucket{
        
            Integer min;
            Integer max;
        }
        public static int getMaxSortedDistance(int[] array){
        
            //1.得到数列的最大值和最小值
            int max = array[0];
            int min = array[0];
            for (int i=0;i<array.length;i++){
        
                if (max<array[i]){
        
                    max = array[i];
                }
                if (min>array[i]){
        
                    min = array[i];
                }
            }
            int d = max - min;
            //如果max和min相等,说明数组所有元素都相等,返回0
            if (d == 0){
        
                return 0;
            }
    
            //2.初始化桶
            int bucketNum = array.length;
            Bucket[] buckets = new Bucket[bucketNum];
            for (int i = 0;i<bucketNum;i++){
        
                buckets[i] = new Bucket();
            }
            //3. 遍历原始数据,确定每个桶的最大值最小值
            for (int i=0;i<array.length;i++){
        
                //确定数组元素所归属的桶下标
                int index = ((array[i] - min) * (bucketNum -1) /d);
                if (buckets[index].min==null || buckets[index].min>array[i]){
        
                    buckets[index].min = array[i];
                }
                if (buckets[index].max == null || buckets[index].max<array[1]){
        
                    buckets[index].max = array[i];
                }
            }
            //4.遍历桶,找到最大差值
            int leftMax = buckets[0].max;
            int maxDistance = 0;
            for (int i=1;i<buckets.length;i++){
        
                if (buckets[i].min == null){
        
                    continue;
                }
                if (buckets[i].min - leftMax > maxDistance){
        
                    maxDistance = buckets[i].min - leftMax;
                }
                leftMax = buckets[i].max;
            }
            return maxDistance;
        }
    
        public static void main(String[] args) {
        
            int[] array = new int[]{
        2,6,3,4,5,10,9};
            System.out.println(getMaxSortedDistance(array));
        }
    }
    
    展开全文
  • 题目:有一个无序整型数组,如何求出这个数组排序后的任意两个相邻元素的最大差值?要求时间和空间复杂度尽可能低。(例如:无序数组 2,3,1,4,6,排序后是1,2,3,4,6,最大差值是6-4=2) 解法一:...

     

    图片

     

     

    图片

     

     

    图片

     

     

    图片

     

     

    小灰一边回忆一边讲述起当时面试的情景......

     

     

     

    图片

     

     

    图片

     

    图片

     

     

    题目:有一个无序整型数组,如何求出这个数组排序后的任意两个相邻元素的最大差值?要求时间和空间复杂度尽可能低。(例如:无序数组 2,3,1,4,6,排序后是1,2,3,4,6,最大差值是6-4=2)

     

     

     

    图片

     

     

    图片

     

     

    解法一:

     

    用一种较快的稳定排序算法(比如归并算法,时间复杂度N*logN)给原数组排序,然后遍历排好序的数组,每两个相邻元素求差,最终得到最大差值。

     

    该解法的时间复杂度是O(N*logN),在不改变原数组的情况下,空间复杂度是O(N)。

     

     

    图片
     

     

    图片

     

     

    图片
     

     

    图片

     

     

    图片
     

     

     

    解法二:

     

    1.利用计数排序的思想,先求出原数组的最大值Max与最小值Min的区间长度k(k=Max-Min+1)。

     

    2.创建一个长度为k的新数组Array。

     

    3.遍历原数组,把原数组每一个元素插入到新数组Array对应的位置,比如元素的值为n,则插入到Array[n-min]当中。此时Array的部分位置为空,部分位置填充了数值。

     

    4.遍历新数组Array,统计出Array中最大连续出现空值的次数+1,即为相邻元素最大差值。

     

    例如给定无序数组 { 2, 6, 3, 4, 5, 10, 9 },处理过程如下图:

     

     

    图片

    图片

     

    图片

     

    图片

     

     

    该解法的时间复杂度为O(n+k),空间复杂度同样是O(n+k)。

     

     

    图片

     

    图片

     

    图片

     

     

    图片

     

     

    图片

     

     

    解法三:

     

    1.利用桶排序的思想,先求出原数组从最小值Min到最大值Max的单位区间长度d,d=(Max-Min)/n。算出d的作用是为了后续确定各个桶的区间范围划分。

     

    2.创建一个长度是N+1的数组Array,数组的每一个元素都是一个List,代表一个桶。

     

    3.遍历原数组,把原数组每一个元素插入到新数组Array对应的桶当中,进入各个桶的条件是根据不同的数值区间(数值区间如何划分,看后面的图就明白了)。由于桶的总数量是N+1,所以至少有一个桶是空的。

     

    4.遍历新数组Array,计算每一个空桶右端非空桶中的最小值,与空桶左端非空桶的最大值的差,数值最大的差即为原数组排序后的相邻最大差值。

     

    例如给定无序数组 { 0, 6, 3, 16, 7, 10, 9, 11, 20, 18 },处理过程如下图:

     

     

     

    图片

     

     

    图片

     

     

    图片

     

     

    图片

     

     

    该解法的时间复杂度为O(n),空间复杂度同样是O(n)。

     

     

    图片

     

     

    十分钟后......

     

     

    图片

     

     

    以上就是小灰面试的情况......

     

     

    图片

     

     

    图片

     

    图片

     

     

     

    展开全文
  • 前言 Spring 也算有多年的历史了,已成为Java应用程序开发框架的事实标准。在如此悠久的历史背景下,有人可能会认为Spring放慢了脚步,躺在了自己的荣誉簿上,再也做不出什么新鲜的东西,或者是让人激动的东西。...

    前言

    Spring 也算有多年的历史了,已成为Java应用程序开发框架的事实标准。在如此悠久的历史背景下,有人可能会认为Spring放慢了脚步,躺在了自己的荣誉簿上,再也做不出什么新鲜的东西,或者是让人激动的东西。甚至有人说,Spring是遗留项目,是时候去看看其他创新的东西了。
    这些人说得不对。
    Spring的生态圈里正在出现很多让人激动的新鲜事物,涉及的领域涵盖云计算、大数据、无模式的数据持久化、响应式编程以及客户端应用程序开发。
    而大厂面试更是年年不会落下问SpringBoot,你还在怕搞不懂SpringBoot吗?以下是小编好时间心思整理的Spring大厂面试从基础到深入必懂知识点,分享出来给大家学习阅读,查漏补缺,也预祝大家面试顺利!

    一,阿里巴巴面试题

    image

    image.gif

    二,百度面试题

    image

    image.gif

    三,蚂蚁金服面试题

    image

    image.gif

    四,美团面试题

    image

    image.gif

    五,携程面试题

    image

    image.gif

    六,所有面试题所得结论

    通过面试题来看,可以看出目前互联网公司面试考点为:

    1. 性能调优、算法数据机构
    2. 高并发下数据安全、接口冪等性、原子性等
    3. 分布式下协同、已经锁的处理
    4. 数据库的分库分表、项目之间的垂直拆分

    最后

    按照上面的过程,4个月的时间刚刚好。当然Java的体系是很庞大的,还有很多更高级的技能需要掌握,但不要着急,这些完全可以放到以后工作中边用别学。

    学习编程就是一个由混沌到有序的过程,所以你在学习过程中,如果一时碰到理解不了的知识点,大可不必沮丧,更不要气馁,这都是正常的不能再正常的事情了,不过是“人同此心,心同此理”的暂时而已。

    道路是曲折的,前途是光明的!”

    g-v4EWyJM3-1624087913283)]

    [外链图片转存中…(img-XaPiw209-1624087913283)]

    更多Java核心笔记、真实面经、学习笔记等知识干货可以点击这里免费领取

    展开全文
  • 求一个无序数组排序后,相邻两个元素的最大差值。 如: {17, 0, 99, 23, 67, 13, 14, 89, 4} 输出: 32 // 77 - 45 思路: 显然先排序,后暴力是可以做出来的,不过,有更好的办法,那就是桶排序。 对于n个数,...
  • 问题一、请使用两种方法对一下数据进行升序,降序排序: arr = [1, 4 ,19, 2, 65]; 方法一: function Arrsort(arr) { for(var i = 0; i < arr.length-1; i++){ for(var j = 0; j<arr.length-i-1; j++){ if...
  • 先将数组从中间分成前后两部分,然后对这两部分分别排序,再将排序之后的数据合并 用递归代码实现归并排序 递推公式: merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r)) 终止条件: p >= r ...
  • 把如下两个无序数组a和b从小到大排序后,在按照从小到大的顺序一次存放到新的数组中。 int a[5]={9,78,33,12,23}; int b[8]={1,34,63,10,5,94,39,27}; **输出格式要求:"%4d\n","%4d" 程序运行示例为: 9 12 23 33 ...
  • php 实现快速排序算法:第一种:1. 选取第一个元素为基数,分别从右(high)往左(high--)查找,找到一个比基数小的数,进行位置交换, 直到 low == ...2. 此时的 low 值代表一次排序后 基数所在的数组下标位置。3. 通过...
  • 无序数组变成有序数组并且去重 面试2:用代码实现无序数组变成有序数组并且去重 例如:{5, 6, 8, 9, 6, 5, 4, 9, 8, 7} 结果:[4, 5, 6, 7, 8, 9] import java.util.*; public class Interview{ public static ...
  • 网上看到文章都说无序数组删除元素慢,其实只要稍作改进就快了。 对于非末尾的元素,需要删除时不要直接删除,把末尾的元素移到它的位置上,再删除末尾的元素,只需要做一次数据移动即可。 ...
  • 基本思路:对数组进行排序,直接访问数组中位数 double MIDnum(vector<int>& array) { if(array.empty()) return -1; int midIndex = (array.size() - 1) / 2; sort(array.begin(), array.end()); if...
  • package test;public class RankKth{/*** invokes this method to allow array containing duplicate elements** @param index* @param direction* @return*/private int moveBound(int index, String direction){if...
  • #includevoid main(){int a[10],b[10],c[20],i,j,t;for(i=0;i<10;i++)scanf("%d",&a[i]);for(i=0;i<...i++)//此为冒泡排序法,网上去百度一下,原理还是比较好理解{for(j=0;j<9-i;j++)...
  • 无序数组元素查找

    2021-06-02 23:35:19
    public class TestBinarySrh{ public static void main(String[] args) { int[] a = {1,2,6,4,3,7,72,25,75,8,9,0,12,10,17,20,35,4}; int srh = 73; int length1 = a.length/2; int length2 = a.length;...
  • 文章目录前言一篇文章、40分钟演示如何将无序数组放到二叉树中01 设计思路:02 冒泡排序:03 二叉树基本概念:04 实战: 前言   如果您觉得有用的话,记得给博主点个赞,评论,收藏一键三连啊,写作不易啊^ _ ^。   ...
  • public class MaxSortedDistance { ... //无序数组排序后的最大相邻差 MaxSortedDistance maxSortedDistance = new MaxSortedDistance(); int[] array = {10, 11}; System.out.println(maxSortedDistance.getMa.
  • 无序数组找中位数

    2021-04-04 09:27:11
    1.无序数组找中位数 思路一 把无序数组排好序,取出中间的元素 时间复杂度 采用普通的比较排序法 O(N*logN) 如果采用非比较的计数排序等方法, 时间复杂度 O(N), 空间复杂度也是O(N). 思路二 (1)将前(n+1)/2个...
  • 首先,在数组中查找指定值,首先想到的就是折半查找法(二分法),但在折半法中,要求数组必须是有序的,所以可以先将数组内的数据进行相关的排序工作后,再运用二分法查找。int BinarySearch(int* array,int size,int...
  • classArray{//定义一个有序数组private long[] a;//定义数组长度private intnElems;//构造函数初始化public Array(intmax){a= new long[max];nElems= 0;}//size函数public intsize(){returnnElems;}//定义添加函数...
  • 数组分为已排序和未排序两部分,每次从未排序中选择最大的元素,放到已排序部分的最末位置,只需进行k次操作,便可得到第k个大的元素,即索引为 [k-1] 的值。 方法3:分治法(借助快排思想) 从数组中随机选择一个数...
  • 由于只要求找出第k大的数,没必要将数组中所有值都排序。 典型解法:快速排序分组。 在数组中找到第k大的元素 取基准元素,将元素分为两个集合,一个集合元素比基准小,另一个比基准大 ,三种情况。 1.比基准大的...
  • 以下摘自百度百科:对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。 由概念可得,对于一个有小到大排序好的数据集,...
  • (HashSet是无序的,TreeSet是有序的) 利用set集合实现无序数组关键代码去重如下所示: public static void main(String[] args) { String[] array = {"a","b","c","c","d","e","e","e","a"}; Set set = new HashSet...
  • 给定一个无序数组,找出数组排序之后,相邻元素之间最大的差值。 如果数组元素个数小于 2,则返回 0。 示例 1: 输入: [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都...
  • //用C语言 编写程序:将[3,5,12,8,20,10,17,4,2,11]这几个数组进行从小到大排序 #include <stdio.h> int main () { int i=0; int j=0; int k; int x; int a[10]={3,5,12,8,20,10,17,4,2,11}; for(i=0;...
  • 要找到第k小的元素,可以先将数组排序,再返回第k[-1]个元素即可,这里排序选择效率较高的归并排序 具体实现: /* author: QGQ description: 对于给定的n个元素的数组a[1..n],要求从中找出第k小的元素。 datetime: ...
  • 求一个无序数组中两个数的下标,他们加起来为给定值 首先这个题是无序的,所以不能用两个指针遍历得到,如果排序之后再遍历,那样复杂度是O(nlogn)而且返回的是原来的下标。所以不能这么做。 只能利用哈希表来用...
  • 办公室发文排序排序,点击控件...1、获得此文件种类排序码最大值,从0到排序码最大值形成一个数组newArr。 2、获取此文件种类所有排序码,并将它们形成数组oldArr。 3、取两个数组中不同的元素并输出,输出的元素就为
  • 给定一个无序数组arr,找到数组中未出现的最小正整数 例如arr = [-1, 2, 3, 4]。返回1 arr = [1, 2, 3, 4]。返回5 [要求] 时间复杂度为O(n)O(n),空间复杂度为O(1)O(1) 示例1 输入 [-1,2,3,4] 返回值 1...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 101,529
精华内容 40,611
关键字:

无序数组排序