在左旋转 K 次后找到数组的第 m 个元素
原文:https://www . geeksforgeeks . org/find-the-mth-element-of-the-array-after-k-left-rotations/
给定非负整数 K 、 M 和带有 N 元素的数组arr【】在 K 左旋转后找到数组的 M 第个元素。
示例:
输入: arr[] = {3，4，5，23}，K = 2，M = 1 输出: 5 解释: 第一次左旋转后的数组 a 1 [ ] = {4，5，23，3} 第二次左旋转后的数组 a 2 [ ] = {5，23，3，4} st 元素左旋转 2 次后为 5。
输入: arr[] = {1，2，3，4，5}，K = 3，M = 2 输出: 5 说明: 左旋转 3 圈后的阵列第二个位置有 5 个。
天真法:思路是执行左旋转操作 K 次，然后找到最终阵的 M 第个元素。
时间复杂度: O(N * K) 辅助空间: O(N)
高效方法:要优化问题，请注意以下几点:
-
If the array is rotated N times it returns the initial array again.
例如，a[ ] = {1，2，3，4，5}，K=5 那么数组经过 5 次左旋转 a 5 [ ] = {1，2，3，4，5}。
因此， Kth 旋转后数组中的元素与原数组中索引 K%N 处的元素相同。
-
The Mth element of the array after K left rotations is
{(K+M–1)% N }第
元素。
下面是上述方法的实现:
C++
``` // C++ program for the above approach
include
using namespace std;
// Function to return Mth element of // array after k left rotations int getFirstElement(int a[], int N, int K, int M) { // The array comes to original state // after N rotations K %= N;
// Mth element after k left rotations // is (K+M-1)%N th element of the // original array int index = (K + M - 1) % N;
int result = a[index];
// Return the result return result; }
// Driver Code int main() { // Array initialization int a[] = { 3, 4, 5, 23 };
// Size of the array int N = sizeof(a) / sizeof(a[0]);
// Given K rotation and Mth element // to be found after K rotation int K = 2, M = 1;
// Function call cout << getFirstElement(a, N, K, M); return 0; } ```
Java 语言(一种计算机语言，尤用于创建网站)
``` // Java program for the above approach import java.util.*; class GFG{
// Function to return Mth element of // array after k left rotations public static int getFirstElement(int[] a, int N, int K, int M) {
// The array comes to original state // after N rotations K %= N;
// Mth element after k left rotations // is (K+M-1)%N th element of the // original array int index = (K + M - 1) % N;
int result = a[index];
// Return the result return result; }
// Driver code public static void main(String[] args) {
// Array initialization int a[] = { 3, 4, 5, 23 };
// Size of the array int N = a.length;
// Given K rotation and Mth element // to be found after K rotation int K = 2, M = 1;
// Function call System.out.println(getFirstElement(a, N, K, M)); } }
// This code is contributed by divyeshrabadiya07 ```
Python 3
```
Python3 program for the above approach
Function to return Mth element of
array after k left rotations
def getFirstElement(a, N, K, M):
# The array comes to original state # after N rotations K %= N
# Mth element after k left rotations # is (K+M-1)%N th element of the # original array index = (K + M - 1) % N
result = a[index]
# Return the result return result
Driver Code
if name == 'main':
# Array initialization a = [ 3, 4, 5, 23 ]
# Size of the array N = len(a)
# Given K rotation and Mth element # to be found after K rotation K = 2 M = 1
# Function call print(getFirstElement(a, N, K, M))
This code is contributed by mohit kumar 29
```
C
``` // C# program for the above approach using System;
class GFG{
// Function to return Mth element of // array after k left rotations public static int getFirstElement(int[] a, int N, int K, int M) {
// The array comes to original state // after N rotations K %= N;
// Mth element after k left rotations // is (K+M-1)%N th element of the // original array int index = (K + M - 1) % N;
int result = a[index];
// Return the result return result; }
// Driver code public static void Main(string[] args) {
// Array initialization int []a = { 3, 4, 5, 23 };
// Size of the array int N = a.Length;
// Given K rotation and Mth element // to be found after K rotation int K = 2, M = 1;
// Function call Console.Write(getFirstElement(a, N, K, M)); } }
// This code is contributed by rutvik_56 ```
java 描述语言
```
// Javascript program for the above approach
// Function to return Mth element of // array after k left rotations function getFirstElement(a , N , K , M) {
// The array comes to original state // after N rotations K %= N;
// Mth element after k left rotations // is (K+M-1)%N th element of the // original array var index = (K + M - 1) % N;
var result = a[index];
// Return the result return result; }
// Driver code
// Array initialization var a = [ 3, 4, 5, 23 ];
// Size of the array var N = a.length;
// Given K rotation and Mth element // to be found after K rotation var K = 2, M = 1;
// Function call document.write(getFirstElement(a, N, K, M));
// This code contributed by gauravrajput1
```
Output:
5时间复杂度:O(1) T5辅助空间:** O(1)
版权属于：月萌API www.moonapi.com，转载请注明出处
