题目描述
最近事情比较少，空闲比较多，就刷刷剑指offer上的经典题。把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 note：给出的所有元素都大于0，若数组大小为0，请返回0。
解题思路
旋转数组：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
二分法：对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。
这道题最简单的做法就是整个数组遍历一遍，找出最小的值，但是这个就没有利用旋转数组的特性了，根据旋转数组的特性，这个数组优势非减排序的，那么最小的那个值刚好是旋转数组的分界线，在排序中我们可以用二分法实现最小值得查找。
代码实现
旋转数组：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,k为3
public static int[] rotate(int[] data, int k)
{
if (data == null) return data;
int temp = 0, length = data.length;
k = k % length;
for (int i = 0; i < k; i++)
{
//依次后移
temp = data[length - 1];
for (int j = length - 1; j > 0; j--)
{
data[j] = data[j - 1];
}
data[0] = temp;
}
return data;
}
优化的旋转数组
public static int[] rotate2(int[] nums, int k)
{
// 处理 k 大于 数组长度的情况
k = k % nums.length;
// 对前 n - k 个元素 [1,2,3,4] 进行逆转后得到 [4,3,2,1]
reverse(nums, 0, nums.length - 1 - k);
//对后k个元素 [5,6,7] 进行逆转后得到 [7,6,5]
reverse(nums, nums.length - k, nums.length - 1);
// 将前后元素 [4,3,2,1,7,6,5] 逆转得到：[5,6,7,1,2,3,4]
reverse(nums, 0, nums.length - 1);
return nums;
void reverse(int[] nums2, int start, int end)
{
while (start < end)
{
int temp = nums2[start];
nums2[start++] = nums2[end];
nums2[end--] = temp;
}
}
}
最简单的方法实现查找最小值
public static int minforsimple(int[] data) {
if (data == null) return 0;
int temp = data[0];
for (int i = 1; i < data.length; i++) {
if (data[i] < temp) {
temp = data[i];
}
}
return temp;
}
二分法查找最小值
public static int minforbinary(int[] data)
{
if (data == null) return 0;
int left = 0;
int right = data.length - 1;
var mid = 0;
while (left < right)
{
mid = (left + right) / 2;
if (data[mid] > data[right]) left = mid + 1;
else if (data[mid] < data[right]) right = mid;
else right = mid;
}
return data[left];
}
把一个数组的偶数排在前面奇数排在后面
public static int[] oddandeven(int[] data) {
if (data == null) return data;
int i = 0,j = data.length - 1;
for (i = 0; i <= j; i++)
{
if (data[i] % 2 == 1)//奇数判断
{
for (int k = j; k > i; k--)
{
if (data[k] % 2 == 0)//偶数判断
{
j = k;
var temp = data[i];
data[i] = data[k];
data[k] = temp;
break;
}
}
}
}
return data;
}
想入非非：扩展思维，发挥想象
1. 熟悉二分法
2. 熟悉旋转数组
3. 把一个数组的偶数排在前面奇数排在后面
测试
using codinginterviews;
using system;
using system.collections.generic;
using system.text;
using xunit;
namespace codingtest
{
public class coding006test
{
/// <summary>
/// 奇数
/// </summary>
[fact]
public void test1() {
int[] array = { 3, 4, 5, 1, 2 };
assert.equal(1, coding006.minforbinary(array));
assert.equal(1, coding006.minforsimple(array));
}
/// <summary>
/// 偶数
/// </summary>
[fact]
public void test2()
{
int[] array = { 3, 4, 5, 1 };
assert.equal(1, coding006.minforbinary(array));
assert.equal(1, coding006.minforsimple(array));
}
/// <summary>
/// 正序
/// </summary>
[fact]
public void test3()
{
int[] array = { 1, 2, 3, 4, 5 };
assert.equal(1, coding006.minforbinary(array));
assert.equal(1, coding006.minforsimple(array));
}
/// <summary>
/// 单数
/// </summary>
[fact]
public void test4()
{
int[] array = { 1};
assert.equal(1, coding006.minforbinary(array));
assert.equal(1, coding006.minforsimple(array));
}
/// <summary>
/// 偶数
/// </summary>
[fact]
public void test5()
{
int[] array = { 1,2 };
assert.equal(1, coding006.minforbinary(array));
assert.equal(1, coding006.minforsimple(array));
}
[fact]
public void test6()
{
int[] array = { 2, 1 };
assert.equal(1, coding006.minforbinary(array));
assert.equal(1, coding006.minforsimple(array));
}
[fact]
public void test7()
{
int[] array = { 3, 4, 5, 2, 2, 2 };
assert.equal(2, coding006.minforbinary(array));
assert.equal(2, coding006.minforsimple(array));
}
[fact]
public void test8()
{
int[] array = { 1, 0, 1, 1, 1 };
assert.equal(0, coding006.minforbinary(array));
assert.equal(0, coding006.minforsimple(array));
}
}
}
其他系列的题
栈和队列:用两个栈实现队列
树:重建二叉树
从尾到头打印链表
字符串替换空格
二维数组中的查找
黄山市民网：https://www.huangshanshimin.com/
