精华内容
下载资源
问答
  • 逆天!对无序数组使用二分查找

    千次阅读 多人点赞 2018-07-17 22:58:46
     所谓的无序数组并不是乱序,我们会遇见很多情况是旋转数组,比如一个递增数组最开始的几个元素挪到数组的最后位置。也可以理解成是两个有序数组的组合。 面试题:打印出旋转数组的最小数字  题目:把一个数组...


      所谓的无序数组并不是乱序,我们会遇见很多情况是旋转数组,比如一个递增数组最开始的几个元素挪到数组的最后位置。也可以理解成是两个有序数组的组合。

    面试题:打印出旋转数组的最小数字

      题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。
      例如数组 {3,4,5,1,2} 为数组 {1,2,3,4,5} 的一个旋转,该数组的最小值为 1。

    方法一:

      要想实现这个需求很简单,我们只需要遍历一遍数组,找到最小的值后直接退出循环。代码实现如下:
     

     public class Test08 {
    
        public static int getTheMin(int nums[]) {
            if (nums == null || nums.length == 0) {
                throw new RuntimeException("input error!");
            }
            int result = nums[0];
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i + 1] < nums[i]) {
                    result = nums[i + 1];
                    break;
                }
            }
            return result;
        }
    
        public static void main(String[] args) {
            // 典型输入,单调升序的数组的一个旋转
            int[] array1 = {3, 4, 5, 1, 2};
            System.out.println(getTheMin(array1));
    
            // 有重复数字,并且重复的数字刚好的最小的数字
            int[] array2 = {3, 4, 5, 1, 1, 2};
            System.out.println(getTheMin(array2));
    
            // 有重复数字,但重复的数字不是第一个数字和最后一个数字
            int[] array3 = {3, 4, 5, 1, 2, 2};
            System.out.println(getTheMin(array3));
    
            // 有重复的数字,并且重复的数字刚好是第一个数字和最后一个数字
            int[] array4 = {1, 0, 1, 1, 1};
            System.out.println(getTheMin(array4));
    
            // 单调升序数组,旋转0个元素,也就是单调升序数组本身
            int[] array5 = {1, 2, 3, 4, 5};
            System.out.println(getTheMin(array5));
    
            // 数组中只有一个数字
            int[] array6 = {2};
            System.out.println(getTheMin(array6));
    
            // 数组中数字都相同
            int[] array7 = {1, 1, 1, 1, 1, 1, 1};
            System.out.println(getTheMin(array7));
        }
    }

      打印结果没什么毛病。不过这样的方法显然不是最优的,我们看看有没有办法找出更加优质的方法处理。

    进阶,方法二:

      有序,还要查找

      找到这两个关键字,我们不免会想到我们的二分查找法,但这个数组旋转后已经不是一个真正的有序数组了,倒像是两个递增的数组组合而成的,我们可以这样思考。

      我们可以设定两个下标 low 和 high,并设定 mid = (low + high)/2(写法一)(这里有一个小点需要注意,mid=low+(high-low)/2(写法二),这个写法是更加合适的,因为在两个数都很大的情况下,low+high有存在数组越界的可能性,写法二则不会越界),下面的代码中还是按照写法一进行编程的。替换成二的话更优。
      
      我们自然就可以找到数组中间的元素 array[mid],如果中间的元素位于前面的递增数组,那么它应该大于或者等于 low 下标对应的元素,此时数组中最小的元素应该位于该元素的后面,我们可以把 low 下标指向该中间元素,这样可以缩小查找的范围。
      同样,如果中间元素位于后面的递增子数组,那么它应该小于或者等于 high 下标对应的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们就可以把 high 下标更新到中位数的下标,这样也可以缩小查找的范围,移动之后的 high 下标对应的元素仍然在后面的递增子数组中。

      因为是有序数组的旋转,所以数组最后的元素一定不大于最初的元素。,所以我们的比较可以只选其中一个,代码中统一选择low所对应的元素进行比较
      不管是更新 low 还是 high,我们的查找范围都会缩小为原来的一半,接下来我们再用更新的下标去重复新一轮的查找。直到最后两个下标相邻,也就是我们的循环结束条件。

      说了一堆,似乎已经绕的云里雾里了,我们不妨就拿题干中的这个输入来模拟验证一下我们的算法。

    1. input:{3,4,5,1,2}
    2. 此时 low = 0,high = 4,mid = 2,对应的值分别是:num[low] = 3,num[high] = 2,num[mid] = 5
    3. 由于 num[mid] > num[low],所以 num[mid] 应该是在左边的递增子数组中。
    4. 更新 low = mid = 2,num[low] = 5,mid = (low+high)/2 = 3,num[mid] = 1;
      high - low ≠ 1 ,继续更新。
    5. 由于 num[mid] < num[high],所以断定 num[mid] = 1 位于右边的自增子数组中;
      更新 high = mid = 3,由于 high - low = 1,所以结束循环,得到最小值 num[high] = 1;

    Java 实现这个思路:

    public class Test08 {
    
        public static int getTheMin(int nums[]) {
            if (nums == null || nums.length == 0) {
                throw new RuntimeException("input error!");
            }
            // 如果只有一个元素,直接返回
            if (nums.length == 1)
                return nums[0];
            int result = nums[0];
            int low = 0, high = nums.length - 1;
            int mid;
            // 确保 low 下标对应的值在左边的递增子数组,high 对应的值在右边递增子数组
            while (nums[low] >= nums[high]) {
                // 确保循环结束条件
                if (high - low == 1) {
                    return nums[high];
                }
                // 取中间位置
                mid = (low + high) / 2;
                // 代表中间元素在左边递增子数组
                if (nums[mid] >= nums[low]) {
                    low = mid;
                } else {
                    high = mid;
                }
            }
            return result;
        }
    
        public static void main(String[] args) {
            // 典型输入,单调升序的数组的一个旋转
            int[] array1 = {3, 4, 5, 1, 2};
            System.out.println(getTheMin(array1));
    
            // 有重复数字,并且重复的数字刚好的最小的数字
            int[] array2 = {3, 4, 5, 1, 1, 2};
            System.out.println(getTheMin(array2));
    
            // 有重复数字,但重复的数字不是第一个数字和最后一个数字
            int[] array3 = {3, 4, 5, 1, 2, 2};
            System.out.println(getTheMin(array3));
    
            // 有重复的数字,并且重复的数字刚好是第一个数字和最后一个数字
            int[] array4 = {1, 0, 1, 1, 1};
            System.out.println(getTheMin(array4));
    
            // 单调升序数组,旋转0个元素,也就是单调升序数组本身
            int[] array5 = {1, 2, 3, 4, 5};
            System.out.println(getTheMin(array5));
    
            // 数组中只有一个数字
            int[] array6 = {2};
            System.out.println(getTheMin(array6));
    
            // 数组中数字都相同
            int[] array7 = {1, 1, 1, 1, 1, 1, 1};
            System.out.println(getTheMin(array7));
    
            // 特殊的不知道如何移动
            int[] array8 = {1, 0, 1, 1, 1};
            System.out.println(getTheMin(array8));
        }
    }

    进阶,方法三:

      前面我们提到在旋转数组中,由于是把递增排序数组的前面的若干个数字搬到数组后面,因为第一个数字总是大于或者等于最后一个数字,而还有一种特殊情况是移动了 0 个元素,即数组本身,也是它自己的旋转数组。这种情况本身数组就是有序的了,所以我们只需要返回第一个元素就好了,这也是为什么我先给 result 赋值为 nums[0] 的原因。

      上述代码就完美了吗?我们通过测试用例并没有达到我们的要求,我们具体看看 array8 这个输入。先模拟计算机运行分析一下:

    1. low = 0, high = 4, mid = 2, nums[low] = 1, nums[high] = 1,nums[mid] = 1;
    2. 由于 nums[mid] >= nums[low],故认定 nums[mid] = 1 在左边递增子数组中;
    3. 所以更新 high = mid = 2,mid = (low+high)/2 = 1;
    4. nums[low] = 1,nums[mid] = 1,nums[high] = 1;
    5. high - low ≠ 1,继续循环;
    6. 由于 nums[mid] >= nums[low],故认定 nums[mid] = 1 在左边递增子数组中;
    7. 所以更新 high = mid = 1,由于 high - low = 1,故退出循环,得到 result = 1;

    但我们一眼了然,明显我们的最小值不是 1 ,而是 0 ,所以当 array[low]、array[mid]、array[high] 相等的时候,我们的程序并不知道应该如何移动,按照目前的移动方式就默认 array[mid] 在左边递增子数组了,这显然是不负责任的做法。

      我们修正一下代码:

    public class Test08 {
    
        public static int getTheMin(int nums[]) {
            if (nums == null || nums.length == 0) {
                throw new RuntimeException("input error!");
            }
            // 如果只有一个元素,直接返回
            if (nums.length == 1)
                return nums[0];
            int result = nums[0];
            int low = 0, high = nums.length - 1;
            int mid = low;
            // 确保 low 下标对应的值在左边的递增子数组,high 对应的值在右边递增子数组
            while (nums[low] >= nums[high]) {
                // 确保循环结束条件
                if (high - low == 1) {
                    return nums[high];
                }
                // 取中间位置
                mid = (low + high) / 2;
                // 三值相等的特殊情况,则需要从头到尾查找最小的值
                if (nums[mid] == nums[low] && nums[mid] == nums[high]) {
                    return midInorder(nums, low, high);
                }
                // 代表中间元素在左边递增子数组
                if (nums[mid] >= nums[low]) {
                    low = mid;
                } else {
                    high = mid;
                }
            }
            return result;
        }
    
        /**
         * 在顺序的情况下,查找数组中的最小值
         *
         * @param nums  数组
         * @param start 数组开始位置
         * @param end   数组结束位置
         * @return 找到的最小的数字
         */
        public static int midInorder(int[] nums, int start, int end) {
            int result = nums[start];
            for (int i = start + 1; i <= end; i++) {
                if (result > nums[i])
                    result = nums[i];
            }
            return result;
        }
    
        public static void main(String[] args) {
            // 典型输入,单调升序的数组的一个旋转
            int[] array1 = {3, 4, 5, 1, 2};
            System.out.println(getTheMin(array1));
    
            // 有重复数字,并且重复的数字刚好的最小的数字
            int[] array2 = {3, 4, 5, 1, 1, 2};
            System.out.println(getTheMin(array2));
    
            // 有重复数字,但重复的数字不是第一个数字和最后一个数字
            int[] array3 = {3, 4, 5, 1, 2, 2};
            System.out.println(getTheMin(array3));
    
            // 有重复的数字,并且重复的数字刚好是第一个数字和最后一个数字
            int[] array4 = {1, 0, 1, 1, 1};
            System.out.println(getTheMin(array4));
    
            // 单调升序数组,旋转0个元素,也就是单调升序数组本身
            int[] array5 = {1, 2, 3, 4, 5};
            System.out.println(getTheMin(array5));
    
            // 数组中只有一个数字
            int[] array6 = {2};
            System.out.println(getTheMin(array6));
    
            // 数组中数字都相同
            int[] array7 = {1, 1, 1, 1, 1, 1, 1};
            System.out.println(getTheMin(array7));
    
            // 特殊的不知道如何移动
            int[] array8 = {1, 0, 1, 1, 1};
            System.out.println(getTheMin(array8));
    
        }
    }

      我们再用完善的测试用例放进去,测试通过。

    总结

      本题其实考察的点挺多的,实际上就是考察对二分查找的灵活运用,不少小伙伴死记硬背二分查找必须遵从有序,而没有学会这个二分查找的思想,这样会导致只能想到循环查找最小值了。
      这个是看自nanchen的公众号,加入了自己的理解写的。就舔着脸标成原创了。大佬勿怪。

    展开全文
  • 主要介绍了python 实现在无序数组中找到中位数方法,具有很好对参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 今天小编就为大家分享一篇关于Java查找不重复无序数组中是否存在两个数字的和为某个值,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
  • 本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法。分享给大家供大家参考,具体如下: 从一个无序的整型数组中选出第k小的数,如k=1为最小数,k=n为最大数。这里数组可以是有重复的值! 下面是自己写的...
  • 无序数组变成有序数组并且去重 面试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 ...

    无序数组变成有序数组并且去重

    面试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 void main(String[] args) {
    		int[] strs = {5, 6, 8, 9, 6, 5, 4, 9, 8, 7};
            //对数组进行排序
            Arrays.sort(strs);
            HashSet hashSet = new HashSet();
            //HashSet不允许储存重复元素
            for (int str : strs) {
                hashSet.add(str);
            }
            Object[] objects = hashSet.toArray();
            System.out.println(Arrays.toString(objects));
        }
    }
    
    展开全文
  • 输入一个无序数组用冒泡排序返回有序数组 public function index17() { $arr=array(1,2,9,99,55,999,88,344,3424,324,24,432,32); $a=count($arr); for($b=0;$b<$a-$b;$b++) { for($i=0;$i<$a-1;$i++)...

    ^_^ 亲爱的客官,如果您觉得本文对您有好处,请移动你的鼠标点点下面的关注我,一起学习,一起分享.~ ^_^输入一个无序数组用冒泡排序返回有序数组

    public function index17()
    {
    	$arr=array(1,2,9,99,55,999,88,344,3424,324,24,432,32);
    	$a=count($arr);
    	for($b=0;$b<$a-$b;$b++)
    	{
    		for($i=0;$i<$a-1;$i++)
    		{
    			if($arr[$i]>$arr[$i+1])
    			{
    				$tep=$arr[$i];
    				$arr[$i]=$arr[$i+1];
    				$arr[$i+1]=$tep;
    			}
    		}
    	}
            print_r($arr); 
    }

     

    展开全文
  • 无序数组元素查找

    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;...
    public class TestHalfSrh{
    	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;
    		String str = null;
    		while(length2/2 > 0){
    			for(int i = length1; i<length2; i++){
    				if(srh == a[i]){
    					str = String.valueOf(i);
    					break;
    				}				
    			}	
    			length2 = length1;
    			length1 = length1/2;
    		}
    		System.out.println(str);	
    	}
    }

    输出结果:

    null

    展开全文
  • // 打乱有序的数组 let arr = [1,2,3,4,5] let newArr = [] var len = arr.length function handleArray(arr) { for(let i =0;i<len;i++) { // 随机生成数组的下标 (0-4) let index = Math.floor(Math.random...
  • 无序数组和有序数组

    千次阅读 2019-05-11 10:34:56
    有序数组的最大的好处在于查找的时间复杂度是O(log n),而无序数组的时间复杂度是O(n)。 有序数组的缺点是插入的世家复杂度是O(n),因为值大的元素需要往后移来给新元素腾位置,相反,无序数组的插入时间...
  • 使用条件: 1. 线性表中的记录必须按关键码有序。 2. 必须采用顺序存储结构。 基本思想: 在有序表中,取中间记录作为比较对象, 若给定值与中间记录的关键码相等,则查找成功。 若给定值小于中间记录的关键码...
  • import java.util.*; public class Main_leastSwapTimes { public static void main(String[] args) { int[] arr = new int[] {3,2,1,4}; int times = function(arr, 0, arr.length-1); ...
  • 无序数组中 两个相同的数 解题思路: 这道题我们可以采用二分法来找到数组中重复的元素下标,输出即可 此方法仅限于寻找数组中只有两个相同的数,局限性比较大,可作为参考 代码如下: import java.util.Arrays; ...
  • 无序数组找重复数字

    2021-03-31 20:55:53
    参考链接????的第4种方法,非常巧妙!
  • 无序数组的中位数

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

    千次阅读 2020-03-08 20:25:08
    题目:如何在无序数组中求最大值和最小值,要求比较的次数尽可能小 这是面经中的一道面试题,如果单纯的来看这道题,我们采用暴力法遍历一遍,对每一个元素与存储的最大值和最小值进行比较,完全就可以解决这个问题...
  • 有序数组和无序数组

    千次阅读 2017-10-13 16:13:15
    14.有序数组的查找时间复杂度时O(lgn),无序数组的时间复杂度是O(N),但是对于插入操作,有序数组的时间复杂度是O(n),因为他需要把比插入数大的都往后移,无序数组插入的时间复杂度为O(1).
  • 无序数组排序,并将某个元素插入到数组对应位置 首先是对无序数组的排序实现 假设数组oldArray中保存的是model,并且以model的number排序,利用系统的方法: NSArray *orderArray = [oldArray ...
  • Java实现有序数组和无序数组

    千次阅读 2018-09-05 20:03:38
    描述: 线性表是其组成元素之间具有线性关系的一种线性结构。...数组是实现顺序存储的基础。在程序设计语言中,数组是一种构造数据类型。          时间复杂度表:   增加 查找 删除 更改 ...
  • 无序数组的查询

    2021-06-29 14:35:58
    #include <stdlib.h> #include <stdio.h> int main() { int nums[10] = {0, 10, 6, 296, 177, 23, 0, 100, 34, 999};//数组 ...//a代表数组下标b代表目标的下标c代表输入的数 ...a++) //在十个数组里循环查.
  • 无序数组求中位数

    千次阅读 2018-12-07 16:34:46
    长度为 n 的无序数组,求中位数,如何尽快的估算出中位数,算法复杂度是多少? 算法 1(建立最小堆): 如果数组中元素有奇数个,可以采用这种算法: 步骤 1 :可以将数组的前 (n+1)//2 个元素,建立 1 个最小堆; ...
  • 无序数组找出数组中的最大和最小值 题目 给定一个无序数组找出数组中的最大和最小值 思路 方法1:蛮力法 定义两个遍历保存最大和最小值max,min初始值为数组的第一个元素然后从1开始遍历查找; 下面就看代码实现: ...
  • 无序数组中找top K 个值

    千次阅读 2019-03-08 22:58:50
    先从原数组中取k个值建立一个堆,然后每次从原数组中拿一个值与堆顶元素进行比较,看是否需要替换,如果替换了,就进行一次堆排序。这样到最后,这个堆中的元素就是top K。 前K大,维护最小堆;前K小,维护最大堆 ...
  • 给定一个无序数组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...
  • 字节跳动面试题.无序数组求最大值

    千次阅读 2020-03-23 15:44:08
    1.对于无序数组a,求a[i]-a[j]的最大值,其中i<j 参考:https://www.cnblogs.com/freedom-wangyb/p/4192611.html package test; import java.util.Arrays; public class FindMax { public static void main...
  • 无序数组中第k大的数 最近工作不是很紧,闲下来学习巩固一下,看到一道面试题,解一下,main方法运行成功, public static void main(String[] args) { int[] a = {62,35,3,78}; int k = 2; int num = 0; for...
  • 文章目录前言一篇文章、40分钟演示如何将无序数组放到二叉树中01 设计思路:02 冒泡排序:03 二叉树基本概念:04 实战: 前言   如果您觉得有用的话,记得给博主点个赞,评论,收藏一键三连啊,写作不易啊^ _ ^。   ...
  • 求一个无序数组中两个数的下标,他们加起来为给定值 首先这个题是无序的,所以不能用两个指针遍历得到,如果排序之后再遍历,那样复杂度是O(nlogn)而且返回的是原来的下标。所以不能这么做。 只能利用哈希表来用...
  • 设计一个查找算法,该算法将在一个给定的无序数组中查找指定的元素,若找到该元素返回true,反之返回false。请分析你所设计算法的时间复杂度。 要求 编写并测试所设计的查找算法 实验报告中还需要包含对所设计算法的...
  • 在一个未排序的数组中,找到第k大的数字. 示例: Input:[3,2,1,5,6,4],k=2 Output:5 解题思路: 快速选择一般用于求解第k个最大元素的问题,可以在O(n).快速选择的实现与快速排序相似, 不过只需要找到第k个大的枢...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 144,036
精华内容 57,614
关键字:

无序数组使用