Array Summary

Algorithm

Array is the basic data structure. Here are some popular algorithm question for array. I've tried some different way (Divide and Conquer or Recursion) to solve these problems.

Content

• Sum of Array (Recursive)
• Get the Max and Min of Array (Divide and Conquer)
• Get the Max and Second Max of Array (Divide and Conquer)
• Find Majority Element
• Find Min Gap between two element in unsorted array
• 求两个有序数组的共同元素
• 求三个数组的共同元素
• 找出数组中唯一的重复元素
• 找出出现奇数次的元素
• 求数组中满足给定和的数对
• 最大子段和
• 最大子段积
• 数组循环移位
• 字符串逆序
• 组合问题
• 合并两个数组
• 重排问题
• 找出绝对值最小的元素

1. Sum of Array

    public static int sum(int[] num, int idx) {
        if(idx==num.length)
            return 0;
        return num[idx]+sum(num, idx+1);
    }

2. Get the Max and Min of Array (Divide and Conquer)

    public static int[] findMaxAndMin(int[] num) {
        return helper(num, 0, num.length - 1);
    }
    private static int[] helper(int[] num, int l, int r) {
        if (l >= r)
            return new int[] { num[l], num[l] };
        if (l + 1 == r)
            return new int[] { Math.min(num[l], num[r]),
                    Math.max(num[l], num[r]) };
        int m = l + ((r - l) >> 1);
        int[] resL = helper(num, l, m);
        int[] resR = helper(num, m + 1, r);
        return new int[] { Math.min(resL[0], resR[0]),
                Math.max(resL[1], resR[1]) };
    }

3. Get the Max and Second Max of Array (Divide and Conquer)

    public static int[] findMaxAndSecondMax(int[] num) {
        if (num == null || num.length == 0)
            return null;
        return helper(num, 0, num.length - 1);
    }
    private static int[] helper(int[] num, int l, int r) {
        if (l >= r)
            return new int[] { num[l], num[l] };
        if (l + 1 == r)
            return new int[] { Math.min(num[l], num[r]),
                    Math.max(num[l], num[r]) };
        int m = l + ((r - l) >> 1);
        int[] resL = helper(num, l, m);
        int[] resR = helper(num, m + 1, r);
        int max, secondMax;
        if (resL[1] > resR[1]) {
            max = resL[1];
            if (resL[0] < resR[1])
                secondMax = resR[1];
            else
                secondMax = resL[0];
        } else {
            max = resR[1];
            if (resL[1] < resR[0])
                secondMax = resR[0];
            else
                secondMax = resL[1];
        }
        return new int[] { secondMax, max };
    }

4. Find Min Gap between two element in unsorted array (Time compexity: O(n))

    public static int findMinGap(int[] num) {
        if (num == null || num.length == 0)
            return 0;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        /*************** Using bucket as sort tool ***************/
        for (int i = 0; i < num.length; i++) {
            min = Math.min(min, num[i]);
            max = Math.max(max, num[i]);
        }
        // set a bucket array with length of range
        int range = max - min;
        int[] bucket = new int[range + 1];
        for (int i = 0; i < num.length; i++)
            bucket[num[i] - min]++;
        // return to original array!!
        int idx = 0;
        for (int i = 0; i < bucket.length; i++)
            while (bucket[i] > 0) {
                num[idx++] = i;
                bucket[i]--;
            }
        /************ End of Sort! ************/
        int minGap = Integer.MAX_VALUE;
        for (int i = 1; i < num.length; i++)
            minGap = Math.min(minGap, num[i] - num[i - 1]);
        return minGap;
    }