LeetCode 41. 缺失的第一个正数，这题在 LeetCode 上虽然属于困难题，但是如果不是因为题目要求算法的时间复杂度应为O(n)，那么这题只能算作简单题。我的解法是：首先将给定数组排序，然后从最小的正数 1 开始判断。在提交前我以为算法的时间复杂度会很差，这时候奇怪的事情发生了。具体代码及运行结果如下：
 
public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        Arrays.sort(nums);
        int target = 1;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == target) {
                target += 1;
            }
        }
        return target;
    }
 

 我对这个 1ms 很是好奇，虽然 LeetCode 上的每次提交结果都会有一定的差异，但经过我多次提交后，执行用时基本还是 1ms。
 
从代码分析来看，算法的时间复杂度就是给数组排序（Arrays.sort() 方法）以及数组的一次遍历（O(n)）。所以肯定是 Arrays.sort() 方法的时间复杂度接近 O(n)。
 
于是我去看了 Arrays.sort() 方法的实现，Java 主要排序方法的 java.util.Arrays.sort()，对于基本数据类型使用三向切分的快速排序，对于引用类型使用归并排序。而三向切分的快速排序的时间复杂度为 N ~ NlogN，很接近 O(n)。
 
因为之前我对排序算法只了解选择排序、冒泡排序、插入排序、归并排序、希尔排序，这些算法的时间复杂度没有一个比得上三向切分的快速排序。所以我就重新对我会的排序算法进行整理以及补充不了解的排序算法，如：快速排序、堆排序等。
 
在找相关资料的过程中，看到了一篇对排序算法总结的很好的文章。https://cyc2018.github.io/CS-Notes/#/notes/%E7%AE%97%E6%B3%95%20-%20%E6%8E%92%E5%BA%8F
 
选择排序
 
从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
 
选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
 
而选择排序又是不稳定的算法，因此不推荐使用选择排序
 
private void sort(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n - 1; i++) {
            // 找到最小元素的下标
            int min = i;
            for(int j = i + 1; j < n; j++) {
                if(nums[j] < nums[min]) {
                    min = j;
                }
            }
            // 将最小元素与第一个元素交换位置
            int tmp = nums[i];
            nums[i] = nums[min];
            nums[min] = tmp;
        }
    }
 
冒泡排序
 
从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。
 
在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。
 
冒泡排序的时间复杂度和选择排序差不多，但是冒泡排序是稳定的。
 
private void sort2(int[] nums) {
        int n = nums.length;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[i] < nums[j]) {
                   int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                }
            }
        }
    }
 
插入排序
 
每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序
 
插入排序是稳定的
 
private void sort3(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = tmp;
                }
            }
        }
    }
 
希尔排序
 
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”
 
关于希尔排序的基本思想请参考其他资料，如：严蔚敏老师的《数据结构》（我们学校讲数据结构和基本算法就是用的这本书）
 
希尔排序是不稳定的
 
private void sort4(int[] nums) {
        int n = nums.length;
        // 初始化步长，并且最后一步的步长也必须是 1
        int h = 1;

        // 确定最大步长
        while (h < n / 3) {
            h = 3 * h + 1;
        }

        while (h >= 1) {
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h; j -= h) {
                    if (nums[j] < nums[j - h]) {
                        int tmp = nums[j];
                        nums[j] = nums[j - h];
                        nums[j - h] = tmp;
                    }
                }
            }
            h = h / 3;
        }
    }
 
归并排序
 
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
 
归并排序的步骤：
 
第一步：申请空间，使其大小为两个已经排序序列的长度之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入合并空间，并移动指针到下一个位置
重复步骤三直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
 
归并排序是稳定的
 
private void mergeSort(int[] nums, int left, int right) {
        // 如果只有一个元素，就不要排序了
        if (left == right) {
            return;
        }else {
            // 取中间的数进行拆分
            int mid = (left + right) / 2;

            // 左边的数不断进行拆分
            mergeSort(nums, left, mid);

            // 右边的数不断进行拆分
            mergeSort(nums, mid + 1, right);

            //合并
            merge(nums, left, mid + 1, right);
        }
    }

    private void merge(int[] nums, int left, int mid, int right) {
        // 左边数组的大小
        int[] leftArr = new int[mid - left];

        // 右边数组的大小
        int[] rightArr = new int[right - mid + 1];

        // 往这两个数组中填充数据
        for (int i = left; i < mid; i++) {
            leftArr[i - left] = nums[i];
        }
        for (int i = mid; i <= right; i++) {
            rightArr[i - mid] = nums[i];
        }

        // 两个指向 leftArr 和 rightArr 初始位置的指针
        int i = 0, j = 0;
        // 指向 nums 数组的第一个元素
        int k = left;

        // 比较两个数组的元素值，哪个小，就把哪个往 nums 数组上放
        while (i < leftArr.length && j < rightArr.length) {
            // 谁比较小，谁将元素放入大数组中，并移动指针，继续比较下一个；等于的情况是保持稳定
            if (leftArr[i] <= rightArr[j]) {
                nums[k] = leftArr[i];
                i++;
                k++;
            }else {
                nums[k] = rightArr[j];
                j++;
                k++;
            }
        }

        //如果左边的数组还没比较完，右边的数都已经完了，那么将左边的数抄到大数组中(剩下的都是大数字)
        while (i < leftArr.length) {
            nums[k] = leftArr[i];
            i++;
            k++;
        }
        //如果右边的数组还没比较完，左边的数都已经完了，那么将右边的数抄到大数组中(剩下的都是大数字)
        while (j < rightArr.length) {
            nums[k] = rightArr[j];
            k++;
            j++;
        }
    }
 
快速排序
 
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 
快速排序是不稳定的
 
private void quickSort(int[] nums, int left, int right) {
        int i = left;
        int j = right;

        // 快速排序中的支点，即该支点左边的元素都比右边的元素要小
        int pivot = nums[(left + right) / 2];

        // 左右两端开始扫描
        while (i <= j) {

            // 寻找直到比支点大的数
            while (pivot > nums[i]) {
                i++;
            }

            // 寻找直到比支点小的数
            while (pivot < nums[j]) {
                j--;
            }

            // 此时已经分别找到了比支点小的数（右边），以及比支点大的数（左边），将它们进行交换
            if (i <= j) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                i++;
                j--;
            }
        }

        // 上面的 while 循环保证了第一趟排序支点的左边比支点小，支点的右边比支点大了

        // "左边"继续排序，直到左边只剩下一个数（递归出口）
        if (left < j) {
            quickSort(nums, left, j);
        }
        // "右边"继续排序，直到右边只剩下一个数（递归出口）
        if (i < right) {
            quickSort(nums, i, right);
        }
    }
 
三向切分快速排序
 
三向切分快速排序是快速排序的一种优化算法之一。对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。三向切分快速排序对于有大量重复元素的随机数组可以再线性时间内完成排序
 
三向切分快速排序是不稳定的
 
private void ThreeWayQuickSort(int[] nums, int left, int right) {
        if (right <= left) {
            return;
        }
        int i = left, j = right;
        int k = left + 1;
        int pivot =  nums[left];
        while (k <= j) {
            if (nums[k] < pivot) {
                int tmp = nums[i];
                nums[i] = nums[k];
                nums[k] = tmp;
                i++;
                k++;
            }else if (nums[k] > pivot) {
                int tmp = nums[k];
                nums[k] = nums[j];
                nums[j] = tmp;
                j--;
            }else {
                k++;
            }
        }
        ThreeWayQuickSort(nums, left, i - 1);
        ThreeWayQuickSort(nums, j + 1, right);
    }
 
堆排序
 
把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。
 
 
第一步：构建堆
 无序数组建立堆最直接的方法是从左到右遍历数组进行上浮操作。一个更高效的方法是从右至左进行下沉操作，如果一个节点的两个节点都已经是堆有序，那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作，可以忽略叶子节点的元素，因此只需要遍历一半的元素即可。
 
 
第二步：交换堆顶元素与最后一个元素，交换之后需要进行下沉操作维持堆的有序状态。
 
 
public void heapSort(int []nums){
        int last = nums.length - 1;
        //N构建大根堆
        //从倒数第二层开始
        for (int i = nums.length /2 - 1 ; i >= 0; i--){
            heapIfy(nums, i, last);
        }
        while (last >= 1){
            swap(nums,0,last--);
            heapIfy(nums,0, last);
        }
    }

    //i 大根堆调整
    public void heapIfy(int[] nums,int i,int last){
        //判断有没有子节点（左孩子）
        int left = i * 2 + 1;
        while (left <= last){
            int right = left + 1;
            //左右节点最大值
            int larger = right <= last && nums[right] > nums[left] ? right : left;
            if(nums[larger] > nums[i]){
                swap(nums, larger, i);
                i = larger;
                left = larger * 2 + 1;
            } else {
                break;
            }
        }
    }

    public void  swap(int []nums,int a,int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
 
堆排序是不稳定的
 
排序算法的比较
 

 快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。

目录
 
 
 
题目描述
 
测试用例
 
题目考点
 
解题思路
 
参考解题
 
补充
 

 
 
题目描述
 
输入一个链表，输出该链表中倒数第k个结点。
 
节点定义如下：
 
public class ListNode {
 
    int val;
 
    ListNode next = null;
 
}
 
测试用例
 
功能测试（第k个节点在链表的中间；第k个节点是链表的头结点；第k个节点是链表的尾结点）
特殊输入测试（链表头结点为空指针；链表的节点总数少于k；k=0）
题目考点
 
考查应聘者对链表的理解。
考查应聘者所写代码的鲁棒性。
解题思路
 
假设整个链表有n个节点，那么倒数第k个节点就是从头开始的第n-k+1个节点。
 
我们定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1步，当第一个指针到达链表的尾节点时，第二个指针正好指向倒数第k个节点。
 
但是为了保持程序的鲁棒性，需要考虑下面三个问题：
 
输入头节点为空指针
链表的节点总数少于k
输入k为0
 
 
参考解题
 
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
            // 输入头节点，k；返回倒数第K个节点
        // 异常处理
        if(head == null || k == 0){
            return null;
        }
        // 定义双指针
        ListNode firstNode = head;
        ListNode secondNode = head;
        // 双指针移动，对移动步数计数，条件值为K-1
        int i = 0 ;
        while(secondNode.next != null){
            secondNode = secondNode.next;
            i++; // 步数计数
            if(i > k-1 ){ // 触发同时移动条件，保持两个指针间距为k-1步
                firstNode = firstNode.next;
            }
        }
        // 遍历完成，secondNode到链表尾部，判断异常
        if(i < k -1 ){
            // 没走到k-1步后指针就走到链表尾巴了，表示链表长度不够k，最多k-1
            return null;
        }
        // 完成指向倒数第k个节点的指针firstNode
        return firstNode;
    }
}
 
复杂度是O(N)
 
补充
 
鲁棒性是指程序能够判断输入是或否合乎规范要求，并对不符合要求的输入予以合理的处理。
 
容错性 是鲁棒性的一个重要体现。
 
提高代码的鲁棒性的有效途径是进行防御性编程，防御性编程是一种编程习惯，是指预见在什么地方可能会出现问题，并为这些可能出现的问题制定处理方式。
 
对于链表的倒数第K个节点都有固定的解法：两个指针，利用 k + (n-(k-1)) = n-1
 
解题思路
 
当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其他一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它在链表上走若干步。

 
n个数全排列根据正数第m个排列找出倒数第m个排列（康托展开）
 
 
 题目要求：把1~n的所有排列按字典序排成一排，从中选出一个排列，假设它是正数第m个排列，希望你能回答倒数的第m个排列是什么？
 
 例如1到3的所有排列是：
 
 1 2 3
 
 1 3 2
 
 2 1 3
 
 2 3 1
 
 3 1 2
 
 3 2 1
 
 若选出的排列是1 2 3，则m=1，而你应该输出的排列是3 2 1.
 
 
 输入描述：
 
 第一行数字n，表示排列的长度
 
 第二行n个数字，表示选出的排列，1<=n<=300000
 
 
 输出描述：
 
 一行n个数字，表示所求的排列

 
题目分析思路：
 
n个数的全排列，一共有n！（阶乘）种可能的排列
根据康托展开的公式：X=an*(n-1)!+an-1*(n-2)!+…+ai*(i-1)!+…+a21!+a10!，反向计算某个排列所在的顺序，
倒数顺序=排列总数-正向顺序+1，根据康托展开的正向思路，计算第几个排列
 全排列剖析：求n个数第k个排序----康托展开
 
Python编程代码如下：
 
# encoding:utf-8
from functools import reduce

N = int(input())
A = [int(i) for i in input().split()]


def func(N):
    # N个数排列组合总数
    align_num = reduce(lambda x, y: x * y, range(1, N + 1))
    # print("align_num:", align_num)
    # 找到排列对应的是第几个
    index = find_align_index(N, A)
    # print("index:",index)
    res_arr = find_nth_align(N, align_num - index + 1)
    print(" ".join(map(str, res_arr)))
    return res_arr


# 计算阶乘
def calc_factorial(n):
    a = 1
    for i in range(1, n + 1):
        a = a * i
    return a


# 查找某个排列对应的是第几个
# 已知是n = 5，求14352是它的第几个序列？
def find_align_index(n, arr):
    index = 0
    i = 1
    while arr:
        j = arr[0]
        arr.remove(j)
        count_min_j = len([i for i in arr if i < j])
        index += count_min_j * calc_factorial(n - i)
        i += 1
    return index + 1


# 查找从n个数的排列中找第m个排列
def find_nth_align(n, m):
    num_arr = list(range(1, n + 1))
    m -= 1
    arr = []
    i = 1
    while len(arr) < n - 1:
        s = m // calc_factorial(n - i)
        r = m % calc_factorial(n - i)
        sort_arr = sorted(num_arr)
        num = sort_arr[s]
        arr.append(num)
        num_arr.remove(num)
        m = r
        i += 1
    arr.append(num_arr[0])
    return arr


if __name__ == '__main__':
    testcase1 = "2,2 1,1 2"
    testcase2 = "3,1 2 3,3 2 1"
    testcase3 = "4,1 3 2 4,4 2 3 1"
    testcase4 = "5,3 1 5 2 4,3 5 1 4 2"

    func(N)

 
运行结果：
 

分享一下我老师大神的人工智能教程！零基础，通俗易懂！http://blog.csdn.net/jiangjunshow

也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！


                 
 
 
 
今天的研究成果。原文看这里：JAVA获得数字(正数和倒数)第几位是什么的方法
 
 
 
 
 
JAVA获得某个数字的最后第几位是什么的方法，比如，1234567890，则获得最后第三位，则返回8
 
 
 

 

  

   

    [java] 
    view plain
     copy
     print
    ?
   
  
  
/** 
 * 获得数字(正数和倒数)第几位是什么的方法。 
 *  
 * @author 老紫竹研究室(laozizhu.com) 
 *  
 */  
public class Test {  
  // 字典，里面保存的是1，10，100，1000..直到long的最大允许位数  
  private static final long[] NUMBERS = new long[19];  
  static {  
    NUMBERS[0] = 1;  
    for (int i = 1; i < 19; i++) {  
      NUMBERS[i] = NUMBERS[i - 1] * 10;  
    }  
  }  
  public static void main(String[] args) {  
    long number = 1234567890123456789L;  
    System.out.println("测试取得倒数第几位");  
    System.out.println(getNumberAtLast(number, 3));  
    System.out.println(getNumberAtLast2(number, 3));  
    System.out.println(getNumberAtLast3(number, 3));  
    int total = 1000000;  
    long begin = System.nanoTime();  
    for (int i = 0; i < total; i++) {  
      getNumberAtLast(number, 3);  
    }  
    System.out.println("getNumberAtLast =" + (System.nanoTime() - begin));  
    begin = System.nanoTime();  
    for (int i = 0; i < total; i++) {  
      getNumberAtLast2(number, 3);  
    }  
    System.out.println("getNumberAtLast2=" + (System.nanoTime() - begin));  
    begin = System.nanoTime();  
    for (int i = 0; i < total; i++) {  
      getNumberAtLast3(number, 3);  
    }  
    System.out.println("getNumberAtLast3=" + (System.nanoTime() - begin));  
    System.out.println("测试取得正数第几位");  
    System.out.println(getNumberAtFirst(number, 3));  
    System.out.println(getNumberAtFirst2(number, 3));  
    begin = System.nanoTime();  
    for (int i = 0; i < total; i++) {  
      getNumberAtFirst(number, 3);  
    }  
    System.out.println("getNumberAtFirst =" + (System.nanoTime() - begin));  
    begin = System.nanoTime();  
    for (int i = 0; i < total; i++) {  
      getNumberAtFirst2(number, 3);  
    }  
    System.out.println("getNumberAtFirst2=" + (System.nanoTime() - begin));  
  }  
  /** 
   * 获得数字的倒数第几位是什么 
   *  
   * @param number 
   *          数字 
   * @param index 
   *          位置 
   * @return 位置上的数字，如果超过了则返回0 
   */  
  public static int getNumberAtLast(long number, int index) {  
    for (; index > 1; index--) {  
      number /= 10;  
    }  
    return (int) (number % 10);  
  }  
  /** 
   * 用字符串的方式进行获得。 
   *  
   * @param number 
   *          数字 
   * @param index 
   *          位置 
   * @return 位置上的数字，如果超过了则返回0 
   */  
  public static int getNumberAtLast2(long number, int index) {  
    String str = Long.toString(number);  
    if (str.length() < index) {  
      return 0;  
    }  
    return str.charAt(str.length() - index) - 0x30; // 数字0的字符形式  
  }  
  /** 
   * 通过字典查找倒数第几个数字 
   *  
   * @param number 
   *          数字 
   * @param index 
   *          位置 
   * @return 位置上的数字，如果超过了则返回0 
   */  
  public static int getNumberAtLast3(long number, int index) {  
    return (int) ((number / (NUMBERS[index - 1])) % 10);  
  }  
  /** 
   * 通过字典获得数字的正数第几位是什么 
   *  
   * @param number 
   *          数字 
   * @param index 
   *          位置 
   * @return 位置上的数字，如果超过了则返回0 
   */  
  public static int getNumberAtFirst(long number, int index) {  
    int place = getNumberIndex(number);  
    number /= NUMBERS[place - index + 1];  
    return (int) (number % 10);  
  }  
  /** 
   * 通过字符串获得数字的正数第几位是什么 
   *  
   * @param number 
   *          数字 
   * @param index 
   *          位置 
   * @return 位置上的数字，如果超过了则返回0 
   */  
  public static int getNumberAtFirst2(long number, int index) {  
    String str = Long.toString(number);  
    return str.charAt(index - 1) - 0x30; // 数字0的字符形式  
  }  
  /** 
   * 根据字典得到某个数字在long范围内的位置。<br> 
   * 比如0-9就在第0位<br> 
   * 10-99 就在第1位。 
   *  
   * @param number 
   *          数字 
   * @return 位置 
   */  
  private static final int getNumberIndex(long number) {  
    return getNumberIndexR(number, 0, 19);  
  }  
  /** 
   * 简单的二分查找法，查找某个数字在字典中的位置 
   *  
   * @param number 
   * @param left 
   * @param right 
   * @return 
   */  
  private static final int getNumberIndexR(long number, int left, int right) {  
    if (right <= left + 1) {  
      return left;  
    }  
    int mid = (right - left) / 2 + left;  
    if (NUMBERS[mid] > number) {  
      return getNumberIndexR(number, left, mid);  
    } else {  
      return getNumberIndexR(number, mid, right);  
    }  
  }  
}  
 
/** * 获得数字(正数和倒数)第几位是什么的方法。 *  * @author 老紫竹研究室(laozizhu.com) *  */public class Test {  // 字典，里面保存的是1，10，100，1000..直到long的最大允许位数  private static final long[] NUMBERS = new long[19];  static {    NUMBERS[0] = 1;    for (int i = 1; i < 19; i++) {      NUMBERS[i] = NUMBERS[i - 1] * 10;    }  }  public static void main(String[] args) {    long number = 1234567890123456789L;    System.out.println("测试取得倒数第几位");    System.out.println(getNumberAtLast(number, 3));    System.out.println(getNumberAtLast2(number, 3));    System.out.println(getNumberAtLast3(number, 3));    int total = 1000000;    long begin = System.nanoTime();    for (int i = 0; i < total; i++) {      getNumberAtLast(number, 3);    }    System.out.println("getNumberAtLast =" + (System.nanoTime() - begin));    begin = System.nanoTime();    for (int i = 0; i < total; i++) {      getNumberAtLast2(number, 3);    }    System.out.println("getNumberAtLast2=" + (System.nanoTime() - begin));    begin = System.nanoTime();    for (int i = 0; i < total; i++) {      getNumberAtLast3(number, 3);    }    System.out.println("getNumberAtLast3=" + (System.nanoTime() - begin));    System.out.println("测试取得正数第几位");    System.out.println(getNumberAtFirst(number, 3));    System.out.println(getNumberAtFirst2(number, 3));    begin = System.nanoTime();    for (int i = 0; i < total; i++) {      getNumberAtFirst(number, 3);    }    System.out.println("getNumberAtFirst =" + (System.nanoTime() - begin));    begin = System.nanoTime();    for (int i = 0; i < total; i++) {      getNumberAtFirst2(number, 3);    }    System.out.println("getNumberAtFirst2=" + (System.nanoTime() - begin));  }  /**   * 获得数字的倒数第几位是什么   *    * @param number   *          数字   * @param index   *          位置   * @return 位置上的数字，如果超过了则返回0   */  public static int getNumberAtLast(long number, int index) {    for (; index > 1; index--) {      number /= 10;    }    return (int) (number % 10);  }  /**   * 用字符串的方式进行获得。   *    * @param number   *          数字   * @param index   *          位置   * @return 位置上的数字，如果超过了则返回0   */  public static int getNumberAtLast2(long number, int index) {    String str = Long.toString(number);    if (str.length() < index) {      return 0;    }    return str.charAt(str.length() - index) - 0x30; // 数字0的字符形式  }  /**   * 通过字典查找倒数第几个数字   *    * @param number   *          数字   * @param index   *          位置   * @return 位置上的数字，如果超过了则返回0   */  public static int getNumberAtLast3(long number, int index) {    return (int) ((number / (NUMBERS[index - 1])) % 10);  }  /**   * 通过字典获得数字的正数第几位是什么   *    * @param number   *          数字   * @param index   *          位置   * @return 位置上的数字，如果超过了则返回0   */  public static int getNumberAtFirst(long number, int index) {    int place = getNumberIndex(number);    number /= NUMBERS[place - index + 1];    return (int) (number % 10);  }  /**   * 通过字符串获得数字的正数第几位是什么   *    * @param number   *          数字   * @param index   *          位置   * @return 位置上的数字，如果超过了则返回0   */  public static int getNumberAtFirst2(long number, int index) {    String str = Long.toString(number);    return str.charAt(index - 1) - 0x30; // 数字0的字符形式  }  /**   * 根据字典得到某个数字在long范围内的位置。<br>   * 比如0-9就在第0位<br>   * 10-99 就在第1位。   *    * @param number   *          数字   * @return 位置   */  private static final int getNumberIndex(long number) {    return getNumberIndexR(number, 0, 19);  }  /**   * 简单的二分查找法，查找某个数字在字典中的位置   *    * @param number   * @param left   * @param right   * @return   */  private static final int getNumberIndexR(long number, int left, int right) {    if (right <= left + 1) {      return left;    }    int mid = (right - left) / 2 + left;    if (NUMBERS[mid] > number) {      return getNumberIndexR(number, left, mid);    } else {      return getNumberIndexR(number, mid, right);    }  }}
 

 
 
 
 
 
运行结果：
 
测试取得倒数第几位
7
7
7
getNumberAtLast =74142943
getNumberAtLast2=379321953
getNumberAtLast3=37117566
测试取得正数第几位
3
3
getNumberAtFirst =136200830
getNumberAtFirst2=375250207

 
 
            



给我老师的人工智能教程打call！http://blog.csdn.net/jiangjunshow