leetcode之33搜索旋转排序数组Golang

题目描述

给你一个整数数组 nums ，和一个整数 target 。

该整数数组原本是按升序排列，但输入时在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• nums 肯定会在某个点上旋转
• -10^4 <= target <= 10^4

算法描述

本题的解题步骤为先将旋转后的数组倒旋回去，然后再用二分查找对target进行查找

二分查找都很简单，主要是前面将旋转的数组倒旋回去，我们又很多方法，例如直接排序，或者使用额外的数组空间，但是如果我们要在原地对数组进行倒旋，也就是不使用额外的空间，那么就采用如下的算法

我们都知道如果两个数是互素的，那么他们可以互为对方的加法生成元，也就是我们可以通过加法的方式，通过确定的次数有一个数生成另一个数的**域（这里是数论的知识，忘了叫什么域来着，反正数p的域是包含0在内的一直到p-1的所有的数），我们可以由0到p-1的任意数一直加上一个与p互素的数q，只要加p次，然后用这个和对p求余，就能得到0到p-1的所有的数

算法如下：

• 首先通过比较原始数组中相邻两个数的大小，如果前面的数大于后面的数，那么旋转到的位置就是这里，我们可以得到旋转的次数
• 然后求数组长度和旋转次数的最大公约数
  • 最大公约数就是我们生成数组长度的域所需要的生成元的个数
  • 然后挑选任意位置的连续的最大公约数那么多的元素通过加法生成域的元素，每个生成元加法的次数为数组长度除以最大公约数所得的商
• 此时的数组就是旋转以前的数组了
  • 通过二分查找就能轻易得出结果了

代码

func search(nums []int, target int) int {
	if len(nums) == 0 {
		return -1
	}
	// 首先看旋转了几次
	rotateTimes := 0
	for i := 0; i < len(nums); i++ {
		if i == len(nums)-1 {
			rotateTimes = 0
			break
		}
		if nums[i] > nums[i+1] {
			rotateTimes = len(nums) - i - 1
			break
		}
	}
	// 然后将数组还原
	// 首先看旋转次数和数组长度是不是互素，通过他们的最大公约数可以确定有几个生成原，每次还原循环次数
	length := len(nums)
	if rotateTimes != 0 {
		// 旋转次数不为0才还原
		cDivisor := 0
		times := rotateTimes
		for {
			if length%times == 0 {
				cDivisor = times
				break
			}
			length, times = times, (length % times)
		}
		recoverTimes := len(nums) / cDivisor
		for i := 0; i < cDivisor; i++ {
			// count:=0
			initIndex := len(nums) - rotateTimes + i
			initValue := nums[initIndex]
			dstIndex := (initIndex + rotateTimes) % len(nums)
			for count := 0; count < recoverTimes; count++ {
				// 更改值
				initValue, nums[dstIndex] = nums[dstIndex], initValue
				// 更改下标
				initIndex, dstIndex = dstIndex, (dstIndex+rotateTimes)%len(nums)
			}
		}
	}
	// 此时的数组就是正常数组了，然后使用二分法查找
	resIndex := 0
	low, high := 0, len(nums)-1
	for low <= high {
		mid := (low + high) / 2
		if nums[mid] == target {
			resIndex = mid
			break
		}
		if nums[mid] < target {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	if low > high {
		// 没有找到
		return -1
	}
	return (resIndex + len(nums) - rotateTimes) % len(nums)
}

leetcode之33搜索旋转排序数组Golang

原文：https://www.cnblogs.com/gyyyl/p/13983316.html