数据分类处理(机试题)

原题目

描述
信息社会，有海量的数据需要分析处理，比如公安局分析身份证号码、 QQ 用户、手机号码、银行帐号等信息及活动记录。

采集输入大数据和分类规则，通过大数据分类处理程序，将大数据分类输出。

请注意本题有多组输入用例。
输入描述：

一组输入整数序列I和一组规则整数序列R，I和R序列的第一个整数为序列的个数（个数不包含第一个整数）；整数范围为0~0xFFFFFFFF，序列个数不限

输出描述：

从R依次中取出R，对I进行处理，找到满足条件的I： I整数对应的数字需要连续包含R对应的数字。比如R为23，I为231，那么I包含了R，条件满足。

按R从小到大的顺序:

(1)先输出R；
(2)再输出满足条件的I的个数；
(3)然后输出满足条件的I在I序列中的位置索引(从0开始)；
(4)最后再输出I。

附加条件：

(1)R需要从小到大排序。相同的R只需要输出索引小的以及满足条件的I，索引大的需要过滤掉
(2)如果没有满足条件的I，对应的R不用输出
(3)最后需要在输出序列的第一个整数位置记录后续整数序列的个数(不包含“个数”本身)

序列I：15,123,456,786,453,46,7,5,3,665,453456,745,456,786,453,123（第一个15表明后续有15个整数）
序列R：5,6,3,6,3,0（第一个5表明后续有5个整数）
输出：30, 3,6,0,123,3,453,7,3,9,453456,13,453,14,123,6,7,1,456,2,786,4,46,8,665,9,453456,11,456,12,786

说明：

30----后续有30个整数
3----从小到大排序，第一个R为0，但没有满足条件的I，不输出0，而下一个R是3
6— 存在6个包含3的I
0— 123所在的原序号为0
123— 123包含3，满足条件

示例1
输入：

15 123 456 786 453 46 7 5 3 665 453456 745 456 786 453 123
5 6 3 6 3 0

输出：

30 3 6 0 123 3 453 7 3 9 453456 13 453 14 123 6 7 1 456 2 786 4 46 8 665 9 453456 11 456 12 786

错误思路

一开始把重点放到这句话上了：

整数范围为0~0xFFFFFFFF，序列个数不限

这个取值范围已经超过了Integer的最大值，所以不能用Integer了。
又看到序列个数不限。脑海里第一个想到是海量数据。
一想到海量数据，就潜意识的给自己指了个方向：

不能遍历查询，不然会很慢

如果想查询快，就得建立查询索引，加上查询条件是包含关系。所以得设计一个数据结构，支持基于输入的数据解析成索引结构，然后支持查询。

一路想下去：

要设计一个多叉树，支持将"123123221"这类数字解析成由数字0到9组成的树型结构。叶子节点记录对应的索引位置。
需要在节点类有一个索引数组，记录实际该值在数组中的位置。
需要在根节点上又一个指针数组，引用所有以它开头的非根节点，设这个List为random，然后有一个HashMap，里面记录了0到9共10个根节点，假设有数组1234. 现在查询key=34. 我只要找到3的根节点。然后再找到random 列表，在里面找到节点4. 就会从根节点直接跳到另外一个节点，这个节点可能不是这棵树的节点，它可能是其他树的节点。
在查询的时候，我要一直往下遍历，图中经过的所有节点，只要该节点有索引值，我就要拿出索引值。同时往上串，再用stack做逆序，就能拿到该字符串的值。

一路想了就开始写代码了，搞了一上午写完了，调试各种报错。我开始怀疑了，是不是过度设计了，我这么做到底是为了什么？

错误总结

这道题题目字太多，迷惑性强。不能太抠字眼，把这个测试题目当需求做了。
一般考题会考算法，算法的三个指标是：时间复杂度，额外空间复杂度，常数项复杂度。我犯错就犯在额外空间复杂度上，且不说题目规模说输入量很大，这部分即使占用空间，也不算作算法的额外空间。而我想的思路，为了所谓的块，引入了太复杂的设计。
太追求所谓的高效，而走入了怪圈。

正确思路

洗洗脸，第二天接着做，觉得需要做以下几点：

解析输入的数据，搞成两个数组。
对查询参数数组做排序，排序后去重。至于排序，参数少的时候可以选择O(N^2)级别的冒泡排序，插入排序，选择排序，参数多的时候，可以选择O(logN)的归并排序，堆排序，快速排序。
遍历去重后的查询数组参数，根据每个查询参数，遍历数据数组。
遍历的过程中，处理好一共发现了多少个，统计有多少个数字，注意边界问题。

写代码的时候注意处理一下细节就好了。

不完美的代码如下：

import java.util.ArrayList;
import java.util.Scanner;

public class Main3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String[] rArray = scanner.nextLine().split(" ");
            String[] iArray = scanner.nextLine().split(" ");


            // 解析查询的数字
            Integer size = Integer.valueOf(iArray[0]);
            int[]  searchKeys = new int[size];
            for (int i = 0; i < size; i++) {
                searchKeys[i] = Integer.valueOf(iArray[i+1]);
            }
            // 对要查询的数字排序
            selectSort(searchKeys);


            // 对要查询的数字去重
            ArrayList params = new ArrayList(searchKeys.length);
            int previous = Integer.MIN_VALUE;
            for (int i = 0; i0; j--) {
//                if (arr[j] < arr[j-1]) {
//                    swap(arr, j, j-1);
//                } else {
//                    break;
//                }
//            }
//        }
//    }
//
//
//    public static void bubbleSort(int[] arr) {
//        if (arr == null || arr.length<2) {
//            return;
//        }
//        for(int i=0; i
//            for(int j=1;j
//                if (arr[j-1] >arr[j]) {
//                    swap(arr, j-1, j);
//                }
//            }
//        }

//    }


//    public static int[] generateRandomArray(int maxSize, int maxValue) {
//        int randomSize = (int) (maxSize * Math.random() + 1);
//        int[] arr = new int[randomSize];
//        for(int i=0; i

数据分类处理(机试题)

大数据系统相关栏目本月热门文章