JavaScript 找到旋转排序数组的旋转次数

旋转排序数组是JavaScript中的一种数组类型，它已被随机数量的位置向左或向右旋转。在本文中，我们将了解如何使用JavaScript语言找到原始排序数组上执行的旋转次数以获得给定的排序数组。在本文中，我们主要涵盖了三种不同的方法。

有不同的方法可以在JavaScript中找到旋转排序数组的旋转次数。让我们一一讨论每种方法。

使用递归方法
使用取模操作方法
重复连接和子字符串方法

我们将通过示例来探索上述所有方法及其基本实现。

方法1：使用递归方法

在这种方法中，我们将开发递归函数，该函数将给出旋转次数。当调用递归函数时，它基本上会检查中间元素是否是最小元素。如果不是，则它将搜索数组的左侧和右侧部分，然后找到所需的旋转次数。

语法：

function functionName(parameters) {  
    // Base case: The condition where the recursion ends.  
    if (baseCaseCondition) {  
        // Return the base case value.  
        return baseCaseValue;  
    } else {  
        // Recursive call: Call the function with updated parameters.  
        return functionName(updatedParameters);  
    }  
}

示例： 在这个示例中，我们将使用递归方法，在旋转排序数组中找到旋转次数。

Javascript

function findRotationCount(arr_input, low_part, high_part) { 
    if (low_part >= high_part) 
        return 0; 
  
    if (arr_input[low_part] <= arr_input[high_part]) 
        return low_part; 
  
    let mid_part = 
        Math.floor((low_part + high_part) / 2); 
    if (arr_input[mid_part] < arr_input[mid_part - 1] 
        && arr_input[mid_part] < arr_input[mid_part + 1]) 
        return mid_part; 
  
    if (arr_input[high_part] > arr_input[mid_part]) 
        return findRotationCount( 
            arr_input, low_part, mid_part - 1); 
  
    else
        return findRotationCount( 
            arr_input, mid_part + 1, high_part); 
} 
let inputArray = [4, 5, 6, 7, 1, 2, 3]; 
let output = 
    findRotationCount( 
        inputArray, 0, inputArray.length - 1); 
console.log("Rotation Count is:", output);

输出

Rotation Count is: 4

方法2：使用模操作的方法

在这个方法中，我们将使用输入旋转数组相对于数组的第一个元素的模操作。当模操作输出变小的索引表示旋转次数。

语法：

a%b

示例：在这个示例中，我们将使用模运算在一个旋转排序数组中找到旋转次数。

JavaScript

function rotationCountUsingModuloOperation(arrInput) { 
    let tempVar = arrInput.length; 
    let minimumIndex = 0; 
    let minimumValue = arrInput[0]; 
    for (let i = 1; i < tempVar; i++) { 
        if (arrInput[i] < minimumValue) { 
            minimumValue = arrInput[i]; 
            minimumIndex = i; 
        } 
    } 
    var rotationCountValue = minimumIndex % tempVar; 
    return rotationCountValue; 
} 
let inputArr = [6, 7, 8, 1, 2, 3, 4, 5] 
let output = rotationCountUsingModuloOperation(inputArr); 
console.log("Rotation Count is:", output);

输出

Rotation Count is: 3

方法3：使用重复的连接和子字符串

首先，我们将输入的或原始数组与自身连接起来。然后，我们将找到与原始数组长度相等的排序子字符串。在完成这一步骤后，重复的排序子字符串的起始索引将包含旋转计数。

语法：

function rotationCountUsingConcat(arrInput) {  
    const dupArray =  
        arrInput.concat(arrInput);  
    const sortedSubstr =  
        dupArray.slice().sort((a, b) => a - b);  
    const rotCountVal =  
        dupArray.indexOf(sortedSubstr[0]);  
    return rotCountVal;  
}

示例: 在这个示例中，rotationCountUsingConcat函数使用连接、排序和索引查找来计算一个循环旋转数组的旋转次数。

Javascript

function rotationCountUsingConcat(arrInput) { 
    const dupArray = 
        arrInput.concat(arrInput); 
    const sortedSubstr = 
        dupArray.slice().sort((a, b) => a - b); 
    const rotCountVal = 
        dupArray.indexOf(sortedSubstr[0]); 
    return rotCountVal; 
} 
const inputArr = 
    [15, 18, 2, 3, 6, 12]; 
const output = 
    rotationCountUsingConcat(inputArr); 
console.log("Rotation Count is:", output);

输出