算法 标签

大文件小内存排序问题(阿里笔试题)

关于大文件小内存的问题很常见,今天心血来潮想试试自己写一下这个代码。

1.生成4G的数字文本文件

通过计算每行的字节大小,累加到4G的话就停止写入

 /**
 * 生成一个4G的文件
 *
 * @param file
 * @throws IOException
 */
public static void makeBigFile(File file) throws IOException {

    FileOutputStream fos = new FileOutputStream(file);

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(fos, "utf-8"));
    // 随机数生成种子
    Random rand = new Random(1);

    long fileByteLength = 0;
    // BIG_FILE_SIZE为4G
    while (fileByteLength < BIG_FILE_SIZE) {

        String randomIntStr = rand.nextInt(1000000000) + "";
        bw.write(randomIntStr);
        bw.newLine();

        // 文件大小等于数字字符串的字符串字节大小加上换行符为两个字节
        fileByteLength += randomIntStr.getBytes().length + 2;

    }

    bw.close();

}

2.将大文件分割为256mb的小文件在内存中进行排序

当超过256mb文件时,即更换另一个新的文件。(第一次写,条件没设置好,结果生成了一百多万个空文件,删除花了N久)

 /**
 * 将大文件拆分为不同的小文件
 *
 * @param bigFile 4G大文件
 * @throws IOException
 */
public static void splitBigFileToSmallFile(File bigFile, String dirStr) throws IOException {

    // 提前创建目录
    File dir = new File(dirStr);

    if (!dir.exists()) {
        dir.mkdirs(); //创建目录
    }

    BufferedInputStream fis = new BufferedInputStream(new FileInputStream(bigFile));

    // 用5M的缓冲读取文本文件
    BufferedReader reader = new BufferedReader(new InputStreamReader(fis, "utf-8"), BUFFER_SIZE);

    String line = null;

    int fileNum = 1;
    long smallFileByteLength = 0;


    File smallFile = new File(dirStr + fileNum + ".txt");
    FileOutputStream fos = new FileOutputStream(smallFile);

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(fos, "utf-8"));

    while ((line = reader.readLine()) != null) {

        smallFileByteLength += getRowByteLength(line);

        bw.write(line);
        bw.newLine();

        // 当文件超过固定大小的话,进行拆分
        if (smallFileByteLength > FILE_LIMIT_SIZE) {

            bw.flush();

            // 文件数递增
            fileNum++;
            // 小文件的字节大小重置为0
            smallFileByteLength = 0;

            smallFile = new File(dirStr + fileNum + ".txt");
            fos = new FileOutputStream(smallFile);
            bw = new BufferedWriter(new OutputStreamWriter(fos, "utf-8"));

        }

        // 避免代码错误生成非常多小文件
        if (fileNum > 20) {
            break;
        }

    }


    bw.flush();
    bw.close();

}

阅读全文 »

常见算法总结 - 二叉树篇

本文总结了常见高频的关于二叉树的算法考察。

1.计算一个给定二叉树的叶子节点数目。

可以采用递归的方式进行累加

public static int calculateTreeNodeNumber(TreeNode treeNode) {

        if (treeNode == null) {
            return 0;
        }

        return calculateTreeNodeNumber(treeNode.left) + calculateTreeNodeNumber(treeNode.right) + 1;

}

2.计算二叉树的深度。

跟上题一样采用递归的方式,但需返回左右子树中较深的深度。

public static int getTreeDepth(TreeNode tree) {

        if (tree == null) {
            return 0;
        }

        int left = getTreeDepth(tree.left);
        int right = getTreeDepth(tree.right);

        return left >= right ? left + 1 : right + 1;
}

阅读全文 »

常见算法总结 - 排序篇

本文总结了常见高频的关于排序的算法考察。

1.冒泡排序

冒泡排序的思想是元素两两比较,将较大或者较小的元素往一端进行移动

 public static void bubble(int[] array) {

        for (int i = 0; i < array.length - 1; i++) {

            for (int j = 0; j + 1 < array.length - i; j++) {

                if (array[j] > array[j + 1]) {

                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;

                }

            }

        }

}

阅读全文 »

常见算法总结 - 链表篇

本文总结了常见高频的关于链表的算法考察。

1.如何找到链表的中间元素?

我们可以采用快慢指针的思想,使用步长为1的慢指针和步长为2的快指针,当快指针抵达链表末尾时,此时慢指针指向的即为中点位置。


public static LinkNode findMiddleByPointer(LinkNode node) {

    LinkNode slow = node;
    LinkNode fast = node;
    // 检测快指针是否可以安全移动
    while (fast.next != null && fast.next.next != null) {

        slow = slow.next;
        fast = fast.next.next;

    }

    return slow;

}

我们还可以采用递归的方式,当递归到最末尾的时候,我们已经能知道链表的长度,此时当递归回去的时候,判断当前递归层级等于链表长度一半的时候,即为链表的重点。

public static void findMiddleByRecursion(LinkNode node, int recursionIndex) {

        if (node.next != null) {
            findMiddleByRecursion(node.next, recursionIndex + 1);
        } else {
            middleIndex = recursionIndex % 2 == 0 ? recursionIndex / 2 : recursionIndex / 2 + 1;
        }

        if (middleIndex == recursionIndex) {
            System.out.println(node.value);
        }

        return;

    }
阅读全文 »

常见算法总结 - 数组篇

1.给定一个数值在1-100的整数数组,请找到其中缺少的数字。

找到丢失的数字 利用byte数组的1或0标记该数字是否被删除,例如byte数组下标为0的数值为1的话,代表数字1存在

public static void findMissNumber1(int[] ints) {
        // 声明一个byte数组
        byte[] isExist = new byte[100];
        for (int i = 0; i < ints.length; i++) {
            // 由于数值比下标大1, 0位置其实代表的是数字1
            isExist[ints[i] - 1] = 1;

        }
        for (int i = 0; i < isExist.length; i++) {
            if (isExist[i] == 0) {
                System.out.println("删除的数字是:" + ++i );
            }
        }
}

我们可以利用1-100的总和为5050,我们依次减掉数据内的所有值,得到的差值即为删除的值

public static void findMissNumber2(int[] ints) {
        int sum = 5050;
        for (int i = 0; i < ints.length; i++) {
            sum -= ints[i];
        }
        System.out.println("删除的数字:" + sum);
}

2.从数组中找出给定目标数字的两数组合。例如数组为{2, 3, 5, 7, 8, 9, 11, 14, 18},给定数字给17,那么数组内的3+14=17。

先利用Set存储对应的数字,然后再遍历数组,假设遍历到数字3的时候,检查set中是否存在(17-3)=14这个数字,如果存在的话,即存在这个组合。

public static void findPairNumber(int[] arrays, int target) {

        Set<Integer> existIntegers = new HashSet<>();
        for (int i = 0; i < arrays.length; i++) {
            existIntegers.add(arrays[i]);
        }
        for (int i = 0; i < arrays.length; i++) {
            if (existIntegers.contains(target - arrays[i])) {
                System.out.println("找到对应的数字组合:" + arrays[i] + "和" + (target - arrays[i]));
                // 去除掉已使用过的数字
                existIntegers.remove(arrays[i]);
            }
        }
    }

3.将数组进行反转。

只需要将数组按中间位置为对称轴进行位置交换即可

public static void reverseArray(int[] arrays) {

    for (int i = 0; i < arrays.length/2; i++) {

        int tmp = arrays[i];
        arrays[i] = arrays[arrays.length -1 - i];
        arrays[arrays.length -1 - i] = tmp;

    }

}
阅读全文 »

随机洗牌的算法 有更新!

今天偶然看到群里的群友说道,面试被问如何将扑克牌随机洗牌输出。笔者觉得这道题挺有意思而且挺开放性,有多种不同的实现方式。然后我就随手写了一个算法,仔细一想这个算法的优化空间挺大,于是又写出三种算法。

第一种

我们通过JDK的随机算法获取一个随机下标,再通过Set集合来判断牌是否有被抽到过,如果抽到过的话,继续进行循环,直到抽到原牌数量为止。

public class ShuffleCard1 {

    public static int[] getShuffleCards(int[] cards) {
        // 获取随机数种子
        Random rand = new Random(System.currentTimeMillis());
        // 用Set集合存储已抽过的牌
        Set<Integer> isExisted = new HashSet();
        // 声明洗牌后数组
        int[] shuffleCards = new int[cards.length];
        // 已抽到的牌数量
        int drawCount = 0;
        // 当抽到的牌数量没达到原牌数组的大小时循环
        while (drawCount < cards.length) {
            // 获取一个随机下标
            int index = rand.nextInt(cards.length);
            // 判断该下标对应的牌是否已被抽过,没有的话,抽出
            if (!isExisted.contains(cards[index])) {
                shuffleCards[drawCount++] = cards[index];
                isExisted.add(cards[index]);
            }
        }
        return shuffleCards;
    }
}
阅读全文 »