在旋转排序数组中找到旋转计数

2021年3月13日15:28:59 发表评论 771 次浏览

本文概述

考虑以递增顺序排序的一组不同数字。阵列(顺时针)旋转了k次。给定这样一个数组, 找到k的值。

例子：

Input : arr[] = {15, 18, 2, 3, 6, 12}
Output: 2
Explanation : Initial array must be {2, 3, 6, 12, 15, 18}. We get the given array after 
rotating the initial array twice.

Input : arr[] = {7, 9, 11, 12, 5}
Output: 4

Input: arr[] = {7, 9, 11, 12, 15};
Output: 0

推荐：请在"实践首先, 在继续解决方案之前。

方法1(使用线性搜索)

如果仔细研究示例, 我们会发现转数等于最小元素的索引。一个简单的线性解决方案是找到最小元素并返回其索引。以下是该想法的C ++实现。

C ++

// C++ program to find number of rotations
// in a sorted and rotated array.
#include<bits/stdc++.h>
using namespace std;
  
// Returns count of rotations for an array which
// is first sorted in ascending order, then rotated
int countRotations( int arr[], int n)
{
     // We basically find index of minimum
     // element
     int min = arr[0], min_index;
     for ( int i=0; i<n; i++)
     {
         if (min > arr[i])
         {
             min = arr[i];
             min_index = i;
         }
     }
     return min_index;
}
  
// Driver code
int main()
{
     int arr[] = {15, 18, 2, 3, 6, 12};
     int n = sizeof (arr)/ sizeof (arr[0]);
     cout << countRotations(arr, n);
     return 0;
}

Java

// Java program to find number of 
// rotations in a sorted and rotated
// array.
import java.util.*;
import java.lang.*;
import java.io.*;
  
class LinearSearch
{
     // Returns count of rotations for an 
     // array which is first sorted in 
     // ascending order, then rotated
     static int countRotations( int arr[], int n)
     {
         // We basically find index of minimum
         // element
         int min = arr[ 0 ], min_index = - 1 ;
         for ( int i = 0 ; i < n; i++)
         {
             if (min > arr[i])
             {
                 min = arr[i];
                 min_index = i;
             }
         } 
         return min_index;
     }
  
     // Driver program to test above functions
     public static void main (String[] args) 
     {
         int arr[] = { 15 , 18 , 2 , 3 , 6 , 12 };
         int n = arr.length;
      
         System.out.println(countRotations(arr, n));
     }
}
// This code is contributed by Chhavi

Python3

# Python3 program to find number
# of rotations in a sorted and
# rotated array.
  
# Returns count of rotations for
# an array which is first sorted
# in ascending order, then rotated
def countRotations(arr, n):
  
     # We basically find index
     # of minimum element
     min = arr[ 0 ]
     for i in range ( 0 , n):
      
         if ( min > arr[i]):
          
             min = arr[i]
             min_index = i
          
     return min_index;
  
  
# Driver code
arr = [ 15 , 18 , 2 , 3 , 6 , 12 ]
n = len (arr)
print (countRotations(arr, n))
  
# This code is contributed by Smitha Dinesh Semwal

C#

// c# program to find number of 
// rotations in a sorted and rotated
// array.
using System;
  
class LinearSearch
{
     // Returns count of rotations for an 
     // array which is first sorted in 
     // ascending order, then rotated
     static int countRotations( int []arr, int n)
     {
         // We basically find index of minimum
         // element
         int min = arr[0], min_index = -1;
         for ( int i = 0; i < n; i++)
         {
             if (min > arr[i])
             {
                 min = arr[i];
                 min_index = i;
             }
         } 
         return min_index;
     }
  
     // Driver program to test above functions
     public static void Main () 
     {
         int []arr = {15, 18, 2, 3, 6, 12};
         int n = arr.Length;
      
     Console.WriteLine(countRotations(arr, n));
     }
}
// This code is contributed by vt_m.

的PHP

<?php
// PHP program to find number 
// of rotations in a sorted 
// and rotated array.
  
// Returns count of rotations 
// for an array which is first 
// sorted in ascending order, // then rotated
function countRotations( $arr , $n )
{
     // We basically find index 
     // of minimum element
     $min = $arr [0];
     $min_index ;
     for ( $i = 0; $i < $n ; $i ++)
     {
         if ( $min > $arr [ $i ])
         {
             $min = $arr [ $i ];
             $min_index = $i ;
         }
     }
     return $min_index ;
}
  
// Driver code
$arr = array (15, 18, 2, 3, 6, 12);
$n = sizeof( $arr );
echo countRotations( $arr , $n );
  
// This code is contributed
// by ajit
?>

输出如下：

2

时间复杂度：

上)

辅助空间：

O(1)

方法2(高效使用

二元搜寻

)

在这里我们也找到最小元素的索引, 但是使用二进制搜索。这个想法基于以下事实：

  • 最小元素是前一个大于它的唯一元素。如果没有先前的元素, 则没有旋转(第一个元素为最小)。我们通过将此条件与第(mid-1)个和第(mid + 1)个元素进行比较来检查此条件。
  • 如果最小元素不在中间(既不是中也不是中+1), 则最小元素位于左半部分或右半部分。
    1. 如果中间元素小于最后一个元素, 则最小元素位于左半部分
    2. 其他最小元素位于右半部分。

下面是从中获取的实现

这里

.

C ++

// Binary Search based C++ program to find number
// of rotations in a sorted and rotated array.
#include<bits/stdc++.h>
using namespace std;
  
// Returns count of rotations for an array which
// is first sorted in ascending order, then rotated
int countRotations( int arr[], int low, int high)
{
     // This condition is needed to handle the case
     // when the array is not rotated at all
     if (high < low)
         return 0;
  
     // If there is only one element left
     if (high == low)
         return low;
  
     // Find mid
     int mid = low + (high - low)/2; /*(low + high)/2;*/
  
     // Check if element (mid+1) is minimum element.
     // Consider the cases like {3, 4, 5, 1, 2}
     if (mid < high && arr[mid+1] < arr[mid])
        return (mid+1);
  
     // Check if mid itself is minimum element
     if (mid > low && arr[mid] < arr[mid - 1])
        return mid;
  
     // Decide whether we need to go to left half or
     // right half
     if (arr[high] > arr[mid])
        return countRotations(arr, low, mid-1);
  
     return countRotations(arr, mid+1, high);
}
  
// Driver code
int main()
{
     int arr[] = {15, 18, 2, 3, 6, 12};
     int n = sizeof (arr)/ sizeof (arr[0]);
     cout << countRotations(arr, 0, n-1);
     return 0;
}

Java

// Java program to find number of 
// rotations in a sorted and rotated
// array.
import java.util.*;
import java.lang.*;
import java.io.*;
  
class BinarySearch
{
     // Returns count of rotations for an array
     // which is first sorted in ascending order, // then rotated
     static int countRotations( int arr[], int low, int high)
     {
         // This condition is needed to handle 
         // the case when array is not rotated 
         // at all
         if (high < low)
             return 0 ;
  
         // If there is only one element left
         if (high == low)
             return low;
  
         // Find mid
         // /*(low + high)/2;*/
         int mid = low + (high - low)/ 2 ; 
  
         // Check if element (mid+1) is minimum
         // element. Consider the cases like
         // {3, 4, 5, 1, 2}
         if (mid < high && arr[mid+ 1 ] < arr[mid])
             return (mid + 1 );
  
         // Check if mid itself is minimum element
         if (mid > low && arr[mid] < arr[mid - 1 ])
             return mid;
  
         // Decide whether we need to go to left 
         // half or right half
         if (arr[high] > arr[mid])
             return countRotations(arr, low, mid - 1 );
  
         return countRotations(arr, mid + 1 , high);
     }
  
     // Driver program to test above functions
     public static void main (String[] args) 
     {
         int arr[] = { 15 , 18 , 2 , 3 , 6 , 12 };
         int n = arr.length;
          
         System.out.println(countRotations(arr, 0 , n- 1 ));
     }
}
// This code is contributed by Chhavi

Python3

# Binary Search based Python3 
# program to find number of 
# rotations in a sorted and
# rotated array.
  
# Returns count of rotations for
# an array which is first sorted 
# in ascending order, then rotated
def countRotations(arr, low, high):
  
     # This condition is needed to 
     # handle the case when array
     # is not rotated at all
     if (high < low):
         return 0
  
     # If there is only one 
     # element left
     if (high = = low):
         return low
  
     # Find mid
     # (low + high)/2 
     mid = low + (high - low) / 2 ; 
     mid = int (mid)
  
     # Check if element (mid+1) is
     # minimum element. Consider 
     # the cases like {3, 4, 5, 1, 2}
     if (mid < high and arr[mid + 1 ] < arr[mid]):
         return (mid + 1 )
  
     # Check if mid itself is 
     # minimum element
     if (mid > low and arr[mid] < arr[mid - 1 ]):
         return mid
  
     # Decide whether we need to go
     # to left half or right half
     if (arr[high] > arr[mid]):
         return countRotations(arr, low, mid - 1 );
  
     return countRotations(arr, mid + 1 , high)
  
# Driver code
arr = [ 15 , 18 , 2 , 3 , 6 , 12 ]
n = len (arr)
print (countRotations(arr, 0 , n - 1 ))    
  
# This code is contributed by Smitha Dinesh Semwal

C#

// C# program to find number of 
// rotations in a sorted and rotated
// array.
using System;
  
class BinarySearch
{
     // Returns count of rotations for an array
     // which is first sorted in ascending order, // then rotated
     static int countRotations( int []arr, int low, int high)
     {
         // This condition is needed to handle 
         // the case when array is not rotated 
         // at all
         if (high < low)
             return 0;
  
         // If there is only one element left
         if (high == low)
             return low;
  
         // Find mid
         // /*(low + high)/2;*/
         int mid = low + (high - low)/2; 
  
         // Check if element (mid+1) is minimum
         // element. Consider the cases like
         // {3, 4, 5, 1, 2}
         if (mid < high && arr[mid+1] < arr[mid])
             return (mid + 1);
  
         // Check if mid itself is minimum element
         if (mid > low && arr[mid] < arr[mid - 1])
             return mid;
  
         // Decide whether we need to go to left 
         // half or right half
         if (arr[high] > arr[mid])
             return countRotations(arr, low, mid - 1);
  
         return countRotations(arr, mid + 1, high);
     }
  
     // Driver program to test above functions
     public static void Main () 
     {
         int []arr = {15, 18, 2, 3, 6, 12};
         int n = arr.Length;
          
     Console.WriteLine(countRotations(arr, 0, n-1));
     }
}
// This code is contributed by vt_m.

的PHP

<?php
// Binary Search based PHP
// program to find number
// of rotations in a sorted
// and rotated array.
  
// Returns count of rotations
// for an array which is 
// first sorted in ascending 
// order, then rotated
function countRotations( $arr , $low , $high )
{
     // This condition is needed 
     // to handle the case when 
     // array is not rotated at all
     if ( $high < $low )
         return 0;
  
     // If there is only 
     // one element left
     if ( $high == $low )
         return $low ;
  
     // Find mid
     $mid = $low + ( $high - 
                    $low ) / 2; 
  
     // Check if element (mid+1)
     // is minimum element. Consider
     // the cases like {3, 4, 5, 1, 2}
     if ( $mid < $high && 
         $arr [ $mid + 1] < $arr [ $mid ])
     return (int)( $mid + 1);
  
     // Check if mid itself 
     // is minimum element
     if ( $mid > $low && 
         $arr [ $mid ] < $arr [ $mid - 1])
     return (int)( $mid );
  
     // Decide whether we need 
     // to go to left half or 
     // right half
     if ( $arr [ $high ] > $arr [ $mid ])
     return countRotations( $arr , $low , $mid - 1);
  
     return countRotations( $arr , $mid + 1, $high );
}
  
// Driver code
$arr = array (15, 18, 2, 3, 6, 12);
$n = sizeof( $arr );
echo countRotations( $arr , 0, $n - 1);
  
// This code is contributed bu ajit
?>

输出如下：

2

时间复杂度：

O(登录n)

辅助空间：

如果我们使用迭代二进制搜索, 则使用O(1)(读者可以参考

二进制搜索文章

用于迭代二进制搜索)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: