当前位置: 凤凰彩票登陆 > 编程知识 > 正文

二分查找算法,旋转数组的蝇头数字

时间:2019-09-27 07:49来源:编程知识
题目链接 题目描述 用两个栈来实现一个队列,完成队列的Push和Pop操作。队列中的元素为int类型。 一个栈就是把队列反过来,那再来一个栈push进第一个栈就“正”过来了。 第一个栈就

题目链接

题目描述

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

 一个栈就是把队列反过来,那再来一个栈push进第一个栈就“正”过来了。
第一个栈就是存下反过来的序列。
 每次push进一个数,要先判断stack2“正”序列是否为空,不为空要还原“反序列”,还要stack1 push进所有的stack2。
 每次pop一个数,把stack1全部push进来,就变成了“正序列”,return stack2的pop即可。
 但是想想,有个小优化,push的时候不用在stack1还原反序列,直接push进stack1,这样在pop的时候判断stack2是否为空,不为空,直接pop,这样把早先“入队列”的pop完,再push stack1的。加了一个判断,简化了第一个栈的操作。
 任何时候pop要判断是否还有元素。

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

import java.util.Stack;

class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        while(!stack2.empty()){
            stack1.push(stack2.pop());
        }
        stack1.push(node);
    }

    public int pop() {
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        while(!stack1.empty()) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}

class Main {

}

然后又用我大JS做了一遍,我大JS,每个数组就是一个栈,233,直接push和pop方法。
注意js对pop() 时两个栈为空的处理。 js 是默认返回 undefined ,其他静态语言一般是报异常。

var stack1 = [],
    stack2 = [];
function push(node) {
    stack1.push(node);
}
function pop() {
    if (!stack2.length&&!stack2.length) {
        //处理
    }
    if (!stack2.length) {
        while (stack1.length) {
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}

/*
// 测试
var arr = [];
arr.push(1)
arr.push(2)
arr.push(3)
console.log(arr);
console.log(arr.pop());*/

二分查找算法是在有序数组中用到较为频繁的一种算法。如果不使用二分算法直接对数组进行遍历,跟每个元素进行比较,其时间复杂度为O(n)。

题意

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

 普通查找时间复杂度为n,出在这里肯定是要找优化的。明显是二分,二分的条件,边界和判断就是关键。
 序列保证是旋转过的,如果长度是2,直接返回右边的。我们现在就找这个边界值,未旋转的非递减序列左边肯定小于右边。现在我们就不断缩小这个边界存在的区间。
 中间元素大于第一个元素,则这个中间元素处于从left开始到中间元素只有一个的序列当中,此时最小元素位于中间元素的后面。
 中间元素小于第一个元素,则这个中间元素“非正常”,左面元素到这个元素之间包含了两个序列,最小的数肯定在中间元素前面。
 我这个二分,是留存mid的,所以最后肯定是分到只剩下两个数,且这两个数一定是旋转的,那么右边就是最小的数。
 eg:
 3 1 2,返回3 1,因为缩小的是“旋转的区间的长度”
 3 4 1,返回4 1,最终的都是右边最小,返回即可。

 

解题思路

使用二分查找思想,可以将时间复杂度由O优化到O。
旋转数组特点:

  • 由左右两个有序数组组成,左边的数组元素都大于等于右边的数组元素,要找的最小元素是右边数组的第一个。
  • 可以采用二分法,拿中间元素与左右两端元素比较,若大于等于l,则中间元素属于左数组,令l=mid;若小于等于r,则中间元素属于右数组,令r=mid。
  • 最终,将l=r-1,而最小元素即为r所指元素,这是终止条件。

考虑特例:

  • 特例1 左旋转为前0个,此时最小元素为第一个,要单独判断这种情况。
  • 特例2 l r mid 三个指向的元素相同,此时无法判断mid要归在左边还是右边,进而影响最终的结果,所以这种情况只能使用顺序查找。

 另外的最坏情况就是有相同的元素,array[l] == array[r] && array[l]

array[mid],不能用条件来缩小查找区间,这时候的序列肯定只有两种数,只能顺序查找,找到第一个小的,直接break即可。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int len = array.length;
        if(len==0)
            return 0;
        int l = 0;
        int r = len-1;
        int mid = 0;
        while(r-l!=1) {
            mid = (l+r)/2;
            if(array[l] == array[r] && array[l] == array[mid]){
                return OtherSolve(array,l,r);
            }
            //当中间比第一个元素大时,最小数在右边,因为右边的最小序列整体都是小于左边的大序列
            if(array[mid]>=array[l])
                l = mid;
            //当中间比第一个元素小时,最小数在左边,最小序列的任何一个数整体都是小于左边的大序列
            else if(array[mid]<=array[l]) {
                r = mid;
            }
        }
        return array[r];
    }
     int OtherSolve(int array[],int l,int r){
        int t = array[l];
        for(int i = l+1; i<=r; i++) {
            if(array[i]<t)
                t = array[i];
        }
        return t;
    }
}

 

相关知识

二分查找的思考:我认为二分查找的关键是首先满足“有序”的条件,方法的精髓则是用数组中间的元素与某些东西比较,达到每次减少一半范围的效果,以将查找复杂度优化到O。

但是二分查找算法则更优,因为其查找的时间复杂度为O(lgn),比如数组{1,2,3,4,5,6,7,8,9}。需要查找元素,用二分查找的算法执行的话,其顺序为:

代码

class Solution {public:    int minNumberInRotateArray(vector<int> rotateArray) {        if (rotateArray.size {            return 0;        }        else if (rotateArray.size {            return rotateArray[0];        }        else if (rotateArray.size {            return rotateArray[0] < rotateArray[1] ? rotateArray[0] : rotateArray[1];        }        else{            size_t l = 0;            size_t r = rotateArray.size() - 1;            if (rotateArray[l] < rotateArray[r]) {//特例1 旋转左边0个                return rotateArray[l];            }            size_t mid;            while (l != r - 1) {                mid =  / 2;                if (rotateArray[l] == rotateArray[r] && mid == rotateArray[l]) {//特例2 三者相等,无法判断mid指向的元素属于左边的有序数组还是右边的有序数组,此时只能采用顺序查找                    break;                }                if (rotateArray[mid] >= rotateArray[l]) {                    l = mid;                }                else if (rotateArray[mid] <= rotateArray[r]) {                    r = mid;                }            }            if (l != r - 1) {//顺序查找                int min = rotateArray[0];                for (int i = 1;i < rotateArray.size {                    if (rotateArray[i] < min) {                        min = rotateArray[i];                    }                }                return min;            }            else {                return rotateArray[r];            }        }    }};

第一步:查找中间元素,即为5。由于5<6,则6必然在5之后的数组元素中,那么就在{6,7,8,9}查找;

第二步:寻找{6,7,8,9}的中位数,选7。由于7>6,则6应该在7左边的数组元素中,那么只剩下6,即找到了。

 

 

说白了二分查找法就是不断将数组进行对半分割,每次拿中间元素和目标值进行比较。

 

案例一:

package cn.imooc.java2;
public class Test02 {
     //定义一个静态方法
     static int binarySerach(int[] array, int key) {
          //定义数组下标的最左
         int left = 0;
         //定义数组下标的最右(下标都是从0开始的,因此需要-1)
         int right = array.length - 1;
         while (left <= right) {
             int mid = (left + right) / 2;
             //判断中间值是否为目标值
             if (array[mid] == key) {
                 return mid;
             }
             else if (array[mid] < key) {
                 left = mid + 1;
             }
             else {
                 right = mid - 1;
             }
         }
         return -1;
     }
    //测试,目标值为7
     public static void main(String[] args) {
          Test02 s = new Test02();
          int[] b={1,5,6,7,8,9,10,12};      
          System.out.println(s.binarySerach(b, 7));
     }
}

注意:每次移动left和right指针的时候,需要在mid的基础上+1或者-1, 防止出现死循环, 程序也就能够正确的运行。并且代码中的判断条件必须是while (left <= right),否则的话判断条件不完整,比如:array[3] = {1, 3, 5};待查找的键为5,此时在(low < high)条件下就会找不到,因为low和high相等时,指向元素5,但是此时条件不成立,没有进入while()中。

 

 

案例二:查找第一个相等的元素

package cn.imooc.java2;
public class Test02 {
     // 查找第一个相等的元素
     static int findFirstEqual(int[] array, int key) {
         int left = 0;
         int right = array.length - 1;
         while (left <= right) {
             int mid = (left + right) / 2;
             if (array[mid] >= key) {
                 right = mid - 1;
             }
             else {
                 left = mid + 1;
             }
         }
         if (left < array.length && array[left] == key) {
             return left;
         }        
         return -1;
     }
     public static void main(String[] args) {
          Test02 s = new Test02();
          int[] b={1,5,6,7,7,7,7,8,9,10,12};         
          System.out.println(s.findFirstEqual(b, 7));
     }
}

凤凰新闻下载,  

案例三:查找最后一个相等的元素

package cn.imooc.java2;
public class Test02 {
     static int findLastEqual(int[] array, int key) {
         int left = 0;
         int right = array.length - 1;
         while (left <= right) {
             int mid = (left + right) / 2;
             if (array[mid] <= key) {
                 left = mid + 1;
             }
             else {
                 right = mid - 1;
             }
         }
         if (right >= 0 && array[right] == key) {
             return right;
         }
         return -1;
     }
     public static void main(String[] args) {
          Test02 s = new Test02();
          int[] b={1,5,6,7,7,7,7,8,9,10,12};         
          System.out.println(s.findLastEqual(b, 7));
     }
}

  

案例四:查找最后一个等于或者小于key的元素。也就是说等于查找key值的元素有好多个,返回这些元素最右边的元素下标;如果没有等于key值的元素,则返回小于key的最右边元素下标。

package cn.imooc.java2;
public class Test02 {
     static int findLastEqualSmaller(int[] array, int key) {
         int left = 0;
         int right = array.length - 1;
         while (left <= right) {
             int mid = (left + right) / 2;
             if (array[mid] > key) {
                 right = mid - 1;
             }
             else {
                 left = mid + 1;
             }
         }
         return right;
     }
     public static void main(String[] args) {
          Test02 s = new Test02();
          int[] b={1,5,6,7,7,7,7,8,9,10,12};         
          System.out.println(s.findLastEqualSmaller(b, 11));
     }
}

 

案例五:查找第一个等于或者大于key的元素。也就是说等于查找key值的元素有好多个,返回这些元素最左边的元素下标;如果没有等于key值的元素,则返回大于key的最左边元素下标。

package cn.imooc.java2;
public class Test02 {
     static int findFirstEqualLarger(int[] array, int key) {
         int left = 0;
         int right = array.length - 1;
         while (left <= right) {
             int mid = (left + right) / 2;
             if (array[mid] >= key) {
                 right = mid - 1;
             }
             else {
                 left = mid + 1;
             }
         }
         return left;
     }
     public static void main(String[] args) {
          Test02 s = new Test02();
          int[] b={1,5,6,7,7,7,7,8,9,10,12};         
          System.out.println(s.findFirstEqualLarger(b, 11));
     }
}

  

案例六:查找第一个大于key的元素,也就是说返回大于key的最左边元素下标。

package cn.imooc.java2;
public class Test02 {
     static int findFirstLarger(int[] array, int key) {
         int left = 0;
         int right = array.length - 1;
         while (left <= right) {
             int mid = (left + right) / 2;
             if (array[mid] > key) {
                 right = mid - 1;
             }
             else {
                 left = mid + 1;
             }
         }
         return left;
     }
     public static void main(String[] args) {
          Test02 s = new Test02();
          int[] b={1,5,6,7,7,7,7,8,9,10,12};         
          System.out.println(s.findFirstLarger(b, 11));
     }
}

  

编辑:编程知识 本文来源:二分查找算法,旋转数组的蝇头数字

关键词:

  • 上一篇:没有了
  • 下一篇:没有了