分类 : .NET技术

最近事情比较少,空闲比较多,就刷刷剑指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));
        }
    }
}

其他系列的题

栈和队列:用两个栈实现队列

树:重建二叉树

从尾到头打印链表

字符串替换空格

二维数组中的查找


分类: .NET技术    访问() .NET技术    Web前端    JAVA开发    HTML基础    数据库    电脑知识    CSS基础
CSS教程-web前端教程-免费教程
HTML教程-web前端教程-免费教程


分类

.NET技术 Web前端 JAVA开发 HTML基础 数据库 电脑知识 CSS基础

随机阅读

DIV+CSS是什么?
java判断字符串是否为空
HTML连载23-属性选择器
DIV CSS字体(font-family)实现字体样式设置
button标签定义及使用说明
零基础学习C语言,怎么入门?
oracle sql like多个条件函数
oracle字段like多个条件
Oracle实现like多个值的查询-Oracle实现like多个值的
c语言用什么软件编写(新手c语言基础知识入门)
oracle字段like多个条件
C语言使用什么软件?
oracle数据库模糊查询匹配多个字符串
oracle的sql语句, like很多行怎么写啊?
oracle中的有四种like有四种字符串比较

最新

零基础学习C语言,怎么入门?
C语言使用什么软件?
c语言用什么软件编写(新手c语言基础知识入门)
Oracle如何实现like多个值的查询
Oracle如何实现like多个值的查询 - 数据库
oracle 多个like条件查询
Oracle中关键字like的使用总结
oracle 中模糊查询对like的代替insrt()函数
oracle数据库模糊查询匹配多个字符串
Oracle如何实现like多个值的查询 - Oracle - 服务器

推荐阅读

c语言中break语句的作用
vscode----vue中HTML代码tab键自动补全
undefined是什么意思啊
C#语言之“string格式的日期时间字符串转为DateTime类型”
DIV CSS字体(font-family)实现字体样式设置
js 中日期 转换成时间戳 例如2013-08-30 转换为时间戳
C语言程序中break是什么意思?
replace和replaceAll是JAVA中常用的交换字符的办法
risk-taking中文是什么意思
html如何实现鼠标悬停显示文字,鼠标移走文字消失。


Copyright © 2017 CSS5.NET教程.CSS5 内容仅用于学习和测试参考。 css5.net All Rights Reserved 蜀ICP备15003849号-16