AndroidX技术栈之算法实践

1、如何找出单链表中的倒数第k个元素？

解题思路：用迭代法，使用两个指针P1和P2，分别指向链表中相聚K个结点的两个节点元素。

步骤：

（1）初始时p1，p2均指向头节点元素。

(2) 然后将P2向前移动K个节点。

（3）之后，以相同的速度移动这两个指针，那么p2会在length-K步后到达尾结点，这时p1就刚好在第length-K个结点也就是倒数第K个结点的位置上。

//单链表的结点类
class LinkListNode {
    //为了简化访问单链表,结点中的数据项的访问权限都设为public
    public int data;
    public LinkListNode next;
    public LinkListNode(int data){
        this.data = data;
    }

}

public class LinkListUtil {
    //LinkListNode head=null;//链表头的引用
    LinkListNode findNode(LinkListNode head, int k) {
        if( k<0 ) {
            return null;
        }
        LinkListNode p1 = head;
        LinkListNode p2 = head;
        //先将P2向前移动k个结点
        for(i = 0; i < k; i++) {
            if (NULL == p2) {
                return NULL;
            }
            else {
                p2 = p2->next;
            }
        }

        if (NULL == P2) 
            return NULL;

        //接着以同样的速度移动p1和p2，当p2抵达链表末尾时，p1指向第K个结点
        while(p2->next != NULL){
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }

}

2、百万数据提取最大的前一百个数据?

解题思路：

方法1. 根据快速排序划分的思想

(1) 递归对所有数据分成[a,b）b（b,d]两个区间，(b,d]区间内的数都是大于[a,b)区间内的数

(2) 对(b,d]重复(1)操作，直到最右边的区间个数小于100个。注意[a,b)区间不用划分

(3) 返回上一个区间，并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分，分为[a2,b2）b2（b2,d2]两个区间，取（b2,d2]区间。如果个数不够，继续(3)操作，如果个数超过100的就重复1操作，直到最后右边只有100个数为止。

方法2. 先取出前100个数，维护一个100个数的最小堆，遍历一遍剩余的元素，在此过程中维护堆就可以了。

具体步骤如下：

step1：取前m个元素（例如m=100），建立一个小顶堆。保持一个小顶堆得性质的步骤，运行时间为O（lgm);建立一个小顶堆运行时间为m*O（lgm）=O(m lgm);

step2:顺序读取后续元素，直到结束。每次读取一个元素，如果该元素比堆顶元素小，直接丢弃。如果大于堆顶元素，则用该元素替换堆顶元素，然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素，因此需要维护堆的代价为(N-m)*O(lgm); 最后这个堆中的元素就是前最大的10W个。时间复杂度为O(N lgm）。

补充：这个方法的说法也可以更简化一些：假设数组arr保存100个数字，首先取前100个数字放入数组arr，对于第101个数字k，如果k大于arr中的最小数，则用k替换最小数，对剩下的数字都进行这种处理。

实现的算法如下：

package BigData;

import java.io.*;
import java.util.PriorityQueue;
import java.util.Queue;

public class FileTest {
    public FileTest() {
    }

    public static void main(String[] args) {
        // madeData();
        sortData();
    }

    private static void sortData() {
        FileReader fr = null;
        BufferedReader br = null;
        Queue<Integer> priorityQueue = new PriorityQueue<Integer>(100);
        try {
            fr = new FileReader("C:/test.txt");
            br = new BufferedReader(fr);
            int temp;
            int temp1;
            String str = null;
            long begin3 = System.currentTimeMillis();
            while ((str = br.readLine()) != null) {
                temp = Integer.valueOf(str);
                if (priorityQueue.size() < 100) {
                    priorityQueue.add(temp);
                } else {
                    temp1 = priorityQueue.poll();
                    if (temp1 < temp) {                        
                        priorityQueue.offer(temp);
                    }else{
                        priorityQueue.offer(temp1);
                    }
                }
                System.out.println("FileReader执行耗时:" + priorityQueue.toString());
            }
            br.close();
            fr.close();
            long end3 = System.currentTimeMillis();
            System.out.println("FileReader执行耗时:" + (end3 - begin3) + " 豪秒");
            System.out.println("FileReader执行耗时:" + priorityQueue.toString());
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
        }
    }

    private static void madeData() {
        FileWriter fw = null;
        int count = 1000000;// 写文件行数
        try {
            fw = new FileWriter("C:/test.txt");
            int temp = (int) (Math.random() * 1000000);
            long begin3 = System.currentTimeMillis();
            for (int i = 0; i < count; i++) {
                temp = (int) (Math.random() * 1000000);
                fw.write(temp + "\r\n");
            }
            fw.close();
            long end3 = System.currentTimeMillis();
            System.out.println("FileWriter执行耗时:" + (end3 - begin3) + " 豪秒");
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
        }
    }
}

方法3. 分块查找

先把100w个数分成100份，每份1w个数。先分别找出每1w个数里面的最大的数，然后比较。找出100个最大的数中的最大的数和最小的数，取最大数的这组的第二大的数，与最小的数比较。

3、ArrayList 如何删除重复的元素？

方法一：

原理：利用HashSet来去重。

/** List order not maintained **/  

  public static void removeDuplicate(ArrayList arrayList) {  
   HashSet set = new HashSet(arrayList);  
   arrayList.clear();  
   arrayList.addAll(set);  
  }

方法二:

原理：新建一个ArrayList，把原list中的元素往新list里面添加，遇到重复的就不添加。

//去除重复元素
public static ArrayList getArrayList(ArrayList list){
    ArrayList newList = new ArrayList();
    Iterator it = list.iterator();
    while(it.hasNext()){
        Object obj = it.next();
        if(!newList.contains(obj)){
            newList.add(obj);
        }
    }
    return newList;
}