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

    千次阅读 多人点赞 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的公众号,加入了自己的理解写的。就舔着脸标成原创了。大佬勿怪。

    展开全文
  • ###解题思路 利用二分思路可以解决 首先寻找一个中位数(mid),如果这个中位数大于其右边的值,那么左半部分一定存在峰值,向左边二分查找 反之,如果这个中位数小于其右边的值,那么其右半部分一定存在峰值,向右二分...

    ### 解题思路

    利用二分思路可以解决

    首先寻找一个中位数(mid),如果这个中位数大于其右边的值,那么左半部分一定存在峰值,向左边二分查找

    反之,如果这个中位数小于其右边的值,那么其右半部分一定存在峰值,向右二分查找

    最终找到结果

    class Solution {
    public:
        int findPeakElement(vector<int>& nums) {
            int l = 0, r = nums.size()-1;
            while(l < r){
                int mid = l + r >> 1;
                if(nums[mid] >= nums[mid+1] ) r = mid;
                else l = mid + 1;
            }
            return l;
        }
    };

     

    展开全文
  • 无序数组的并发搜索的实现可以充分的用到多cpu的优势一种简单的策略是将原始数组按照期望的线程数进行分割,如果我们计划使用两个线程进行搜索,就可以把一个数组分成两个,每个线程各自独立的搜索,当其中有一个...

    对无序数组的并发搜索的实现可以充分的用到多cpu的优势

    一种简单的策略是将原始数组按照期望的线程数进行分割,如果我们计划使用两个线程进行搜索,就可以把一个数组分成两个,每个线程各自独立的搜索,当其中有一个线程找到数据后,立即返回结果的index即可。

    首先index需要采用atomicinteger来进行修饰,默认初始化的值为-1,意义为当前未找到,由于内部采用CAS机制,线程在遍历比较是否相等之前,会通过atomicinteger中的get方法拿到当前的值,如果大于等于0,那么说明别的线程已经找到了结果,直接返回get值就可以。如果比较的过程中发现相等了,那么调用atomicinteger中的compareAndSet(-1,i),如果方法返回成功,则说明当前的线程是第一个发现结果的,那么返回当前index即可,如果失败,则说明别的线程先获得了结果,直接返回atomicinteger中的get方法获取的值即可。

    整个过程采用future实现,拿到了Future后,不断地轮询结果,如果大于0即返回结果。

    具体实现:

    packageparallel;importjava.util.ArrayList;importjava.util.List;importjava.util.concurrent.Callable;importjava.util.concurrent.ExecutionException;importjava.util.concurrent.ExecutorService;importjava.util.concurrent.Executors;importjava.util.concurrent.Future;importjava.util.concurrent.atomic.AtomicInteger;public class SeatchTask implements Callable{static int[] arr = {2,34,5,6};static ExecutorService pool =Executors.newCachedThreadPool();static final int Thread_Num = 2;static AtomicInteger result = new AtomicInteger(-1);intbegin,end,searchValue;public static int search(int searchValue, int beginPos, intendPos){int i = 0;for(i = beginPos; i < endPos;i ++){if(result.get() > 0){returnresult.get();

    }if(arr[i] ==searchValue){if(!result.compareAndSet(-1, i)){returnresult.get();

    }returni;

    }

    }return -1;

    }

    @Overridepublic Integer call() throwsException {int re =search(searchValue, begin, end);returnre;

    }public SeatchTask(int searchValue, int begin, intend){this.searchValue =searchValue;this.begin =begin;this.end =end;

    }public static int pSearch(int searchValue) throwsInterruptedException, ExecutionException{int subArrSize = arr.length/Thread_Num + 1;

    List> re = new ArrayList>();for(int i = 0;i < arr.length;i +=subArrSize){int end = i +subArrSize;if(end <= arr.length) end =arr.length;

    re.add(pool.submit(newSeatchTask(searchValue, i, end)));

    }for(Futurefu : re){if(fu.get() >= 0){returnfu.get();

    }

    }return -1;

    }public static void main(String[] args) throwsInterruptedException, ExecutionException {int index = pSearch(34);

    System.out.println(index);

    }

    }

    展开全文
  • import java.util.Scanner;/*** 类似与求第k小的问题* 求第...* https://blog.csdn.net/qq_32767041/article/details/86099117** 这里使用快速选择算法,这是一种基于快速排序的算法,* 在实现上比BFPRT更简单。* htt...

    import java.util.Scanner;

    /**

    * 类似与求第k小的问题

    * 求第k大相当于求第n-k+1小,n为数组长度

    *

    * 著名的BFPRT算法可保证在线性时间内得到结果。

    * https://blog.csdn.net/qq_32767041/article/details/86099117

    *

    * 这里使用快速选择算法,这是一种基于快速排序的算法,

    * 在实现上比BFPRT更简单。

    * https://blog.csdn.net/qq_32767041/article/details/86300744

    *

    * @author wylu

    */

    public class Main {

    public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);

    while (scanner.hasNext()) {

    String[] strs = scanner.nextLine().split(" ");

    int[] arr = new int[strs.length];

    for (int i = 0; i < arr.length; i++) {

    arr[i] = Integer.valueOf(strs[i]);

    }

    int k = scanner.nextInt();

    System.out.println(arr[quickSelect(arr, arr.length - k + 1)]);

    }

    }

    /**

    * 查找第k小元素

    * @param arr 无序数组

    * @param k 目标第k小

    * @return 成功:返回第k小元素的索引

    *         失败:返回-1

    */

    public static int quickSelect(int[] arr, int k) {

    int left = 0, right = arr.length - 1, idx;

    while (left <= right) {

    idx = partition(arr, left, right);

    if ((k - 1) == idx) return idx;

    else if ((k - 1) > idx) left = idx + 1;

    else right = idx - 1;

    }

    return -1;

    }

    /**

    * 对给定的数组区间进行划分

    * @param arr 数组

    * @param left 区间下限,包含arr[left]

    * @param right 区间上限,包含arr[right]

    * @return 返回划分后,划分基准的索引

    */

    private static int partition(int[] arr, int left, int right) {

    int j = left - 1;

    for (int i = left; i < right; i++) {

    if (arr[i] <= arr[right]) swap(arr, i, ++j);

    }

    swap(arr, ++j, right);

    return j;

    }

    private static void swap(int[] arr, int i, int j) {

    int tmp = arr[i];

    arr[i] = arr[j];

    arr[j] = tmp;

    }

    }

    展开全文
  • 使用条件: 1. 线性表中的记录必须按关键码有序。 2. 必须采用顺序存储结构。 基本思想: 在有序表中,取中间记录作为比较对象, 若给定值与中间记录的关键码相等,则查找成功。 若给定值小于中间记录的关键码...
  • 有序数组最大的好处在于查找的时间复杂度是O(log n),而无序数组是O(n)。  有序数组的缺点是插入操作的时间复杂度是O(n),因为值大的元素需要往后移动来给新元素腾位置。相反,无序数组的插入操作时间复杂度...
  • 其实说是无序数组,其实也是使用队列按照输入的顺序插入,和输出。 数据如下: S E A R C H E X A M P L E 结果如下: * S 0 * H 5 * X 7 * R 3 * C 4 * L 11 * A 8 * M 9 * P 10 * E 12 代码如下...
  • 无序数组排序

    千次阅读 2015-11-13 15:28:06
    一直到n的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂度为O(1),使用交换,而且一次只能交换两个数#include using namespace std; int main() { int arr[10]={10,6,9,5,2,8,4,7,1,3}; int len=sizeof...
  • 题目:已知有一个无序数组中存在重复的元素,要求去掉重复元素后输出新数组。 分析: set中的元素是不能重复的。所以我们可以先判断set中有没有该元素,如果没有就进行添加到set中,直到遍历完所有数组元素,最后...
  • 查找 k = 3 小的数 输入:arr[] = {7, 10, 4, 3, 20, 15} 输出:7在一个无序数组,查找 k = 4 小的数 输入:arr[] = {7, 10, 4, 3, 20, 15} 输出:10几种思路如下和复杂度分析如下:(1)最简单的思路直接使用快排,...
  • 无序数组的中位数

    2019-04-22 11:32:00
    无序数组的中位数不能使用排序算法,而且要求时间复杂度O(n)。# -*- coding: utf-8 -*-​# @Time : 2019/4/22 10:42 AM# @Author : George# @File : main7.py# @Contact : georgewang1994@163.com​​def heapify...
  • 如题:给定一个无序数组,如何查找第K小的值。 例子如下: 在一个无序数组,查找 k = 3 小的数 输入:arr[] = {7, 10, 4, 3, 20, 15} 输出:7 在一个无序数组,查找 k = 4 小的数 输入:arr[] = {7, 10, 4,...
  • 问题:给定一个无序数组,找出该无序数组的第k大元素。 思路:1.先排序,那么第k个元素自然就是第k大的元素了。 2.使用最小堆,先利用前k个元素建立最小堆,再往后比较,如果有比堆顶元素大的,则调整最小堆,最后...
  • 1、求一个无序数组的中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置。要求:不能使用排序,时间复杂度尽量低 2、例如: lists = [3, 2, 1, 4] , 中位数为 = ...
  • 题目:找出无序数组中第Kth大的数,如{63,45,33,21},第2大的数45。 输入: 第一行输入无序数组,第二行输入K值。 该是内推滴滴打车时(2017.8.26)的第二题,也是《剑指offer》上最小k个数的变形。当时一看到题...
  • 题目:求一个无序数组的中位数。 如:{2,5,4,9,3,6,8,7,1}的中位数为5,{2,5,4,9,3,6,8,7,1,0}的中位数为4和5。 要求:不能使用排序,时间复杂度尽可能高 提示:考虑堆或者快排思想解决。
  • 最近看了《漫画算法》这本书,小灰大神这...(例如:无序数组 2,3,1,4,6,排序后是1,2,3,4,6,最大差值是6-4=2) 解法一: 先使用时间复杂度为O(nlogn)的排序算法给原来数组排序,然后遍历数组,对每两个相邻元素求...
  • 找出无序数组的最长连续子数组

    千次阅读 2017-08-04 13:59:18
    有这样一个数组,[-4, -3, -2, -1, ...我的思路:1、将数组元素放入二叉树 2、对二叉树使用中序排列,得到一个有序数组 3、对有序数组元素进行-1判断,获得最长连续数组。 具体代码: 1、Node类,二叉树元素   pub
  • 无序数组中,三个数的乘积最大

    千次阅读 2017-10-07 19:41:03
    给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大,要求时间复杂度:O(n),空间复杂度:O(1) 输入,一个无序数组长度n,接着n个数4 3 4 1 2输出,最大的结果24ac1:(时间复杂度 O(nlogn) ...
  • n个整数的无序数组,找到每个元素后面比它大的第一个数,要求时间复杂度为O(N) 今天看到的这样的一题,感觉...从函数可以看出传入的无序数组使用vector来存储的,而且我们需要返回一个vector 一开始拿到题目,我们很...
  • 求一个无序数组的中位数中位数是将数组排序之后,数组个数为奇数时,取中间的即为中位数;数组个数为偶数时,取中间两个的平均值即为中位数。思路一:要取得中位数,即给数组排序,使用任意排序算法均可,然后按数组...
  • 求一个无序数组的中位数

    千次阅读 2017-08-03 17:33:07
    求一个无序数组的中位数 中位数是将数组排序之后,数组个数为奇数时,取中间的即为中位数;数组个数为偶数时,取中间两个的平均值即为中位数。 思路一: 要取得中位数,即给数组排序,使用任意排序算法均可,然后按...
  • 无序数组的并发搜索的实现可以充分的用到多cpu的优势 一种简单的策略是将原始数组按照期望的线程数进行分割,如果我们计划使用两个线程进行搜索,就可以把一个数组分成两个,每个线程各自独立的搜索,当其中有一...
  • 一、题目描述 有一个无序整型数组,如何求出该数组排序后的任意两个相邻元素的最大差值?要求时间复杂度和空间复杂度尽可能的...# 无序数组求最大相邻差 def QuickSort(arr=[],left=None,right=None): left=0 if not
  • python 实现在无序数组中找到中位数

    千次阅读 2019-07-16 21:32:11
    1,求一个无序数组的中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置。要求:不能使用排序,时间复杂度尽量低 2, 例如: lists = [3, 2, 1, 4] , 中位数为 ...
  • 使用一种时间复杂度为O(logn)的排序算法将无序数组排好序 然后在依次求相邻元素的差,并保存最大的差值。 这种方法肯定能解决该问题,但是这样做的算法时间复杂度太高,接近O(n*n)。 public int bruteForce(int ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,265
精华内容 906
关键字:

无序数组使用