精华内容
下载资源
问答
  • 旋转数组

    2019-10-18 19:02:42
    数组旋转 旋转数组查找最小值

    数组旋转
    在这里插入图片描述

    旋转数组查找最小值
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 方法(1):直接遍历...

     

    题目描述

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

    方法(1):直接遍历,找到最小值。

    class Solution {
    public:
        int minNumberInRotateArray(vector<int> rotateArray) {
            int length=rotateArray.size();
                if (length==0)
                    return 0;
            int min = rotateArray[0];
            for (int i=1;i<length;i++)
            {
                if (rotateArray[i]<min)
                {
                    min=rotateArray[i];
                }
            }
            return min;
        }
    };

    方法(2)利用二分查找。如果中间元素值>最后一个元素值,说明最小值右半区间,如果中间元素<最后一个元素区间,说明最小值在左半区间,如果相等说明有相同元素,需要将判断区间往前缩一下,继续判断,不断循环,当二分查找的的左右区间相等了,就说明找到最小值了。

    class Solution {
    public:
        int minNumberInRotateArray(vector<int> rotateArray) {
            int length=rotateArray.size();
                if (length==0)
                    return 0;
            int left=0;
            int right=length-1;
            while(left<right)
            {
                int mid=left+(right-left)/2;
                if (rotateArray[mid]>rotateArray[right])
                {
                    left=mid+1;
                }
                else if (rotateArray[mid]<rotateArray[right])
                {
                    right=mid;
                }
                else 
                    right=right-1;
            }
            return rotateArray[left];
        }
    };

     

    展开全文
  • 189. 旋转数组 题目描述 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。 要求使用空间复杂度为 O(1) 的 原地 算法。 思路 ...

    189. 旋转数组

    题目描述

    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
    尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
    要求使用空间复杂度为 O(1) 的 原地 算法。

    思路

    首先确定移动多少个,k = k % n.(移动长度有可能超过数组长度,所以求余)

    1. 找到下标是n-k的元素,将数组分为两半,分别反转这两部分,最后反转整个数组。
    2. 数组整体向右移动一位,这样做k次即可。
    3. 交换,左下标是0的为起始位与右下标是n-k的交换,左右向右进1,前k个都这样做,然后起始结点加k,重复上面的过程,然后起始结点右加k,直到遍历掉整个数组

    思路一代码:

    import java.util.*;
    public class Solution {
        public int[] solve (int n, int m, int[] a) {
            m = m % n;
            if(a.length == 0 || a.length == 1){
                return a;
            }
            reverse(a,n-m,n-1);
            reverse(a,0,n-m-1);
            reverse(a,0,n-1);
            return a;
        }
        
        public void reverse(int[] arr, int left, int right){
            int temp ;
            while(left < right){
                temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
    }
    

    思路二代码:

    import java.util.*;
    public class Solution {
        public int[] solve (int n, int m, int[] a) {
            m = m % n;
            for(int i = 0; i < m; i++){
                int temp = a[n-1];
                for(int j = n - 2; j >= 0; j--){
                    a[j+1] = a[j];
                }
                a[0] = temp;
            }
            return a;
        }
    }
    
    展开全文
  • 6. 旋转数组的最小数字 &剑指 Offer 11. 旋转数组的最小数字 题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 ...

    6. 旋转数组的最小数字 & 剑指 Offer 11. 旋转数组的最小数字

    题目描述

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

    法一:

    暴力搜索, 遍历数组,后一个数字比前一个数字小的就是那个最小的数字, 如果遍历数组没找到这样的数字,说明所有元素都相等,直接返回numbers[0]

     1 class Solution {
     2     public int minArray(int[] numbers) {
     3          // 遍历数组,后一个数字比前一个数字小的就是那个最小的数字
     4          int len = numbers.length;
     5          for(int i = 0; i < len - 1; i++){
     6              if(numbers[i] > numbers[i+1]){
     7                  return numbers[i+1];
     8              }
     9          }
    10          // 如果遍历数组没找到这样的数字,说明所有元素都相等,直接返回numbers[0]
    11          return numbers[0];
    12     }
    13 }
    

    leetcode运行时间为

    复杂度分析:

    时间复杂度:最坏情况下需要遍历整个数组,所以时间复杂度为O(n)

    空间复杂度:O(1)

    法二:

    利用二分法的变形

    分析:二分查找变种,没有具体的值用来比较。那么用中间值和高低位进行比较,看处于递增还是递减序列,进行操作缩小范围。

    1. 处于递增:low上移

    2. 处于递减:high下移(如果是high-1,则可能会错过最小值,因为找的就是最小值)

    3. 其余情况:low++缩小范围

    特殊情况:

    图片说明
     1 import java.util.ArrayList;
     2 public class Solution {
     3     public int minNumberInRotateArray(int [] array) {
     4         // 从头到尾扫描,记录前一个值大于后一个值的位置
     5         if(array.length <= 0)
     6             return 0;
     7         // 变形的二分查找
     8         int low = 0, high = array.length - 1;
     9         int mid;
    10         while(low < high){
    11             mid = (high - low) / 2 + low;
    12             if(array[low] < array[high])
    13                 return array[low];
    14             if(array[mid] > array[low]){
    15                 low = mid + 1;
    16             }else if(array[mid] < array[high]){
    17                 high = mid;
    18             }else{
    19                 low++;
    20             }
    21         }
    22        return array[low];
    23     }
    24 }
    

    思路三

    这个方法其实和思路二一样,只不过这里是让array[mid]与array[high]比较,如果array[mid] < array[high], 说明mid在右半段有序数组中,那应该high = mid; 如果array[mid] > array[high],说明mid在左半段有序数组中,执行low = mid + 1, 如果array[mid] == array[high],无法确定mid在哪个有序数组中,执行hight--来缩小范围。

     1 class Solution {
     2     public int minArray(int[] numbers) {
     3          // 二分法
     4          int left = 0, right = numbers.length-1;
     5          int mid = 0;
     6          while(left < right){
     7              mid = (right + left) / 2;
     8             if(numbers[mid] > numbers[right]){  // 说明mid在左半段,旋转点在它后面
     9                 left = mid + 1;
    10             }else if(numbers[mid] < numbers[right]){    // 说明mid在右半段,mid可能刚好是旋转点也可能旋转点在mid左侧
    11                 right = mid;
    12             }else{
    13                 right--;        // 无法确定mid的位置,也无法确定旋转点的位置
    14             }
    15          }
    16          return numbers[left];
    17     }
    18 }
    

    leetcode运行时间为0ms- 100.00%, 空间为38.6MB - 65.80%

    复杂度分析:

    时间复杂度:正常情况下二分法的算法复杂度为O(logn), 但是如果这个数组中含有大量重复元素,那么就必须通过right--来缩小范围,这样算法复杂度就降成了O(n)

    空间复杂度:需要的空间都是常量级的,所以空间复杂度为O(1)

    展开全文
  • 剑指 Offer 11. 旋转数组的最小数字 ...旋转数组的最小值与最大值构成旋转数组的分界线。 numbers类似 [1,0,1,1,1] 或者[1,1,1,0,1],此时最小数字不好判断在mid左边 right–. class Solution { public i
  • 搜索旋转数组

    2020-04-27 12:03:42
    搜索旋转数组 来源: LeetCode 面试题 10.03. 搜索旋转数组 题目描述 面试题 10.03. 搜索旋转数组 搜索旋转数组。给定一个排序后的数组,包含n个整数,但这个数组已被旋转过很多次了,次数不详。请编写代码找出数组...
  • 旋转数组的最小数字 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组...
  • 输入一个递增排序的数组的一个旋转, 输出旋转数组的最小元素。例如数组{3,4,5,1,2 }为{ 1,2,3,4,5}的一个旋转,该数组的最小值为1。 二、解题思路 Step1.和二分查找法一样,我们用两个指针分别指向数组的第一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,360
精华内容 5,744
关键字:

旋转数组