5.6号刷题

第一题 Arrary561ArrayPairSum

算法

求解将2n个数组合后的最小值, 解法1，排序后隔一个取

public int arrayPairSum(int[] nums) {
    Arrays.sort(nums);
    int sum = 0;
    for (int i = 0; i < nums.length; i = i + 2) {
        sum += nums[i];
    }
    return sum;
}

算法证明:

Assume in each pair i, bi >= ai.
Denote Sm = min(a1, b1) + min(a2, b2) + … + min(an, bn). The biggest Sm is the answer of this problem. Given 1, Sm = a1 + a2 + … + an.
Denote Sa = a1 + b1 + a2 + b2 + … + an + bn. Sa is constant for a given input.
Denote di = |ai - bi|. Given 1, di = bi - ai. Denote Sd = d1 + d2 + … + dn.
So Sa = a1 + a1 + d1 + a2 + a2 + d2 + … + an + an + di = 2Sm + Sd => Sm = (Sa - Sd) / 2. To get the max Sm, given Sa is constant, we need to make Sd as small as possible.
So this problem becomes finding pairs in an array that makes sum of di (distance between ai and bi) as small as possible. Apparently, sum of these distances of adjacent elements is the smallest. If that’s not intuitive enough, see attached picture. Case 1 has the smallest Sd.

学到的东西:

Arrary排序： Arrays.sort(arraryname);

第二题 Arrary566Mattrix Reshape

算法

自己的算法

将所有的数字取出来，推进Queue然后再进行重构。效率太低，时间复杂度2n^2,空间复杂度n

int row = nums.length;
int column = nums[0].length;
System.out.print(row + " " + column);

if (r * c > row * column) {
    return nums;
}

Queue<Integer> numbers = new ArrayDeque<>();
for (int i = 0; i < row; i++)
    for (int j = 0; j < column; j++)
        numbers.add(nums[i][j]);

int[][] result = new int[r][c];
for (int i = 0; i < r; i++)
    for (int j = 0; j < c; j++)
        result[i][j] = numbers.poll();
return result;

算法2下标逐渐相加

int row = nums.length, column = nums[0].length;
if ( row * column != r * c) return nums;

int[][] result = new int[r][c];
int index_r = 0, index_c = 0;

for (int i = 0; i < row; i++)
    for (int j = 0; j < column; j++) {
        result[index_r][index_c] = nums[i][j];
        index_c += 1;
        if (index_c == c) {
            index_r +=1;
            index_c = 0;

        }
    }
    return result;

算法3求余获得相应位置

算法的核心是将原数组的行列，通过除法和求余进行新位置的对应，因此只需要一次循环便可以完成整个过程。

int row = nums.length, column = nums[0].length;
if ( row * column != r * c) return nums;

int[][] result = new int[r][c];
for (int i = 0; i < row * column; i++)
    result[i/c][i%c] = nums[i/column][i%column];

return result;

学到的东西

Queue的实现链接

Queue<Integer> numbers = new ArrayDeque<>();

二维数组赋值, 附上一个写的较好的链接

int[][] num = {{1,2},{3,4}};

第三题 Arrary280WiggleSort

我的算法

进行排序后，按照大小交换顺序

int[] sorted = nums.clone();
Arrays.sort(sorted);
int end = sorted.length - 1;
int begin = 0;
for (int i = 0; i < nums.length; i++) {
    if (i % 2 == 0) {
        nums[i] = sorted[begin];
        begin++;
    } else {
        nums[i] = sorted[end];
        end--;
    }
}

高效算法

利用前后进行交换，如果不满足条件，便交换前后的大小

for (int i = 0; i < nums.length; i++) {
    if (i % 2 ==1) {
        if (nums[i-1] > nums[i]) {
            int temp = nums[i-1];
            nums[i-1] = nums[i];
            nums[i] = temp;
        }
    } else if (i != 0 && nums[i] > nums[i-1]) {
        int temp = nums[i-1];
        nums[i-1] = nums[i];
        nums[i] = temp;
    }
}

第四题 Arrary324WiggleSort II

算法

算法是将数组先进性排序，之后先找到中位数，之后按照顺序进行插入。具体顺序链接

pupublic void wiggleSort(int[] nums) {
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    for (int i = (nums.length - 1)/2, j = 0; i >= 0; i--, j += 2) {
        nums[j] = sorted[i];
    }
    for (int i = nums.length - 1, j = 1; i > (nums.length - 1)/2; i--, j +=2) {
        nums[j] = sorted[i];
    }
}

第五题 Arrary370

算法

自己的

对应的index的值相加，但是代码的效率很低

int iteration = updates.length;
int[] result = new int[length];
for (int i = 0; i < iteration; i++) {
    for (int j = updates[i][0]; j <= updates[i][1]; j++) {
        result[j] += updates[i][2];
    }
}
return result;

改进

在加的时候根据index，记录下每个index在开始的值，之后再用一个sum求和函数将之前积累的值算出来。这样的办法，时间复杂度只有O(K+N)

int[] result = new int[length];
for (int[] update : updates) {
    int start = update[0];
    int end = update[1];
    int value = update[2];
    result[start] += value;
    if (end < length - 1) result[end+1] -= value;
}
int sum = 0;
for (int i = 0; i < length; i++) {
    sum += result[i];
    result[i] = sum;
}
return result;

学到的东西

for 循环中，可以对for(int[] a : b)进行循环, b为二维矩阵。