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

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

## 本文概述

``````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``````

## 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)

)

• 最小元素是前一个大于它的唯一元素。如果没有先前的元素, 则没有旋转(第一个元素为最小)。我们通过将此条件与第(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)