题目
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为0，请返回-1。
样例

输入：nums=[2,2,2,0,1]
输出：0
算法：

(二分) O(n)

为了便于分析，我们先将数组中的数画在二维坐标系中，横坐标表示数组下标，纵坐标表示数值，如下所示：


图中水平的实线段表示相同元素。
我们发现除了最后水平的一段（黑色水平那段）之外，其余部分满足二分性质：竖直虚线左边的数满足 nums[i]≥nums[0]；而竖直虚线右边的数不满足这个条件。

分界点就是整个数组的最小值。
所以我们先将最后水平的一段删除即可。
另外，不要忘记处理数组完全单调的特殊情况：
当我们删除最后水平的一段之后，如果剩下的最后一个数大于等于第一个数，则说明数组完全单调。

时间复杂度分析

二分的时间复杂度是 O(logn)，删除最后水平一段的时间复杂度最坏是 O(n)，所以总时间复杂度是 O(n)。
class Solution {
    public int findMin(int[] nums) {
        int n = nums.length - 1;
        if(n < 0) return -1;
        #去除右端水平黑线
        while(n > 0 && nums[n] == nums[0]) n--;
        #如果右端为空的话那么就只剩竖直虚线左半部分，最小的就是最左端
        if(nums[n] >= nums[0]) return nums[0];
        int l = 0,r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
}

在数组x的十个数中求平均值v，找出与v相差最小的数组元素（题目来源：c语言程序设计第三版）
#include<stdio.h>
#include<math.h>
int main()
{
	double a[10],aver,sum,det[10],min;
	int i;
	for(i=0;i<10;i++)
	{
	printf("请输入一个数：\n");
	scanf("%lf",&a[i]);
	sum+=a[i];
	}
	aver=sum/10;
	for(i=0;i<10;i++)
	{
		det[i]=aver-a[i];
		det[i]=fabs(det[i]);
	}
	min=a[0];
	for(i=1;i<10;i++)
	{
		if(det[i]<=det[i-1])
		min=a[i];
	}
	printf("该数组的平均值v=%lf\n",aver);
	printf("与平均数差值最小的数组元素为%lf",min);
	return 0;
}

对于两个或者多个数与平均值的差相等的情况下，还不能完备地全部输出值，需要改进。

把数组排成最小的数

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解题思路:

把数字转换为字符串，然后cmp比较大小，升序排列后输出。

cmp(x,y) 函数用于比较2个对象，如果 x < y 返回 -1, 如果 x == y 返回 0, 如果 x > y 返回 1

代码:

 map 与lambda关系参考：https://www.jianshu.com/p/07737690901e

# -*- coding:utf-8 -*-
#把数组排成最小的数
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        import operator
        if not numbers:
            return ''
        numbers = list(map(str, numbers))#转为字符串
        numbers.sort(cmp=lambda x,y: int(x+y)-int(y+x))#数字比较
        if numbers[0] == '0':
            return 0
        else:
            return ''.join(numbers)

丑数

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解题思路：

按顺序把每个丑数放在数组中，求下一个丑数。下一个丑数必定由有数组中的某一个丑数A * 2， B * 3， C * 5 的中的最小值得来。

分析：在数组中必定有一个丑数M2， 在它之前的数 * 2 都小于当前最大丑数， 在它之后的数 * 2都大于当前最大丑数，

同样有M3, M5

代码:

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index<1:
            return 0 
        res = [1]
        t2 = t3 = t5 = 0
        nextdex = 1
        while nextdex < index:
            minNum = min(res[t2]*2, res[t3]*3, res[t5]*5)
            res.append(minNum)
            #step步伐很小，每一个数都考虑到
            while res[t2]*2 <= minNum:
                t2 +=1
            while res[t3]*3<= minNum:
                t3 +=1
            while res[t5]*5 <= minNum:
                t5 +=1
                
            nextdex +=1
        return res[nextdex-1]

第一个只出现一次的字符

题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

解题思路:

先对每个字符出现的字符进行个数统计，然后再对原字符串进行遍历，找出第一个出现次数为1的字符

代码:

# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        from collections import Counter
        count = Counter(s)
        if not s:
            return -1
        for i,c in enumerate(s):
            if count[c] == 1:
                return i 

 

找出数组中最大（小）的十个数
最小（大）堆实现
思路
快速排序实现
思路
注意

最小（大）堆实现
思路
要找出数组中最大的10个数，建立一个容量为10的最小堆，遍历数组，当最小堆容量小于10的时候直接push，当容量大于10的时候，数组的数和最小堆的堆顶的数进行比较，如果小于堆顶数则不可能是最大的10个数之一，如果大于则和堆顶数进行交换，一直遍历完数组
import java.util.Random;
class Test {
	private static int ptr = 1;
	private static int[] heap= new int[6];
	private static int[] num = new int[30];

	public static void main(String[] args) {
		Random rand = new Random();
		for(int i = 0; i < 30; i++) {
			num[i] = rand.nextInt(100);
			System.out.println(num[i]);
		}
		for(int i = 0; i < 30; i++) {
			push(num[i]);
		}
		System.out.println();
		for(int i = 1; i < 6; i++) {
			System.out.println(heap[i]);
		}
	}
	
	public static void push(int x) {
		if(ptr <= 5) {
			heap[ptr++] = x;
			adjustUp(ptr-1);
		} else {
			if(x <= heap[1]) {
				return;
			} 
			heap[1] = x;
			adjustDown();
		}	
	}


	public static void adjustDown() {
		for(int i = 1; i * 2 <= 5; ) {
			int next = 2*i;
			if(next+1 <= 5 && heap[next] > heap[next+1]) {
				next++;
			}
			if(heap[i] > heap[next]) {
				swap(heap, i, next);
				i = next;
			} else {
				return;
			}
		}
	}

	public static void adjustUp(int current) {
		for(int i = current; i > 1; i /= 2) {
			if(heap[i] < heap[i/2]) {
				swap(heap, i, i/2);
			} else {
				return;
			}
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j] ;
		arr[j] = temp;
	}
}

快速排序实现
思路
快速排序的时候是先找到一个中间数，这个中间数的左边的数都比这个数小，中间数的右边的数都比这个数大，当要找出最小的10个数的时候，只要找出中间数等于10，它左边的所有数就是最小的十个数
注意

一定可以得到中间数是我们想要的数量，因为快速排序是一直递归进行直到得到两个数的快排或者一个数的快排
得到中间数有两种情况，一种是 low == high 即将返回的时候，另一种是继续递归的时候，这两种情况都有可能，都要考虑，不然只在某些情况输出结果，某些情况没有输出

import java.util.Random;
class Test{
	private static int[] arr = new int[30];
	public static void main(String[] args) {
		Random rand = new Random();
		for(int i = 0; i < 30; i++) {
			arr[i] = rand.nextInt(100);
		}
		quickSort(arr, 0, 29);
	}
	
	public static void quickSort(int[] num, int low, int high) {
		if(low >= high) {
			//第一种情况
			if(low == 5)  {
				for(int i = 0; i < 5; i++) {
					System.out.println(arr[i]);
				}
			}
			return;
		}
		int middle = getMiddle(num, low, high);
		//第二种情况
		if(middle == 5)  {
			for(int i = 0; i < 5; i++) {
				System.out.println(arr[i]);
			}
		}
		quickSort(num, low, middle-1);
		quickSort(num, middle+1, high);
	}

	public static int getMiddle(int[] num, int low, int high) {
		int temp = num[low];
		while(low < high) {
			while(low < high && num[high] >= temp) high--;
			num[low] = num[high];
			while(low < high && num[low] <= temp) low++;
			num[high] = num[low];
		}
		num[low] = temp;
		return low;
	}
}