顺序表内容如下：
class ArrayList {
public int[] arr;
public int length;
public ArrayList(int[] arr, int length) {
if (arr.length < length) {
throw new IllegalArgumentException();
}
this.arr = arr;
this.length = length;
}
@Override
public String toString() {
if (length == 0) return "[]";
StringBuilder sb = new StringBuilder();
sb.append("[").append(arr[0]);
for (int i = 0; i < length; i++) {
sb.append(", ").append(arr[i]);
}
sb.append("]");
return sb.toString();
}
}
所有函数都放在类中。
1、删除最小元素public int deleteMin() {
if (length == 0) {
throw new IllegalArgumentException("顺序表长度为0，无法删除。");
}
int minIndex = 0;
for (int i = 0; i < length; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
int temp = arr[minIndex];
length--;
arr[minIndex] = arr[length - 1];
return temp;
}
这个题有点离谱，题上说是返回被删除的元素，但是给的答案却是返回删除是否成功的布尔值。
后来再看了一下答案，原来他还传参了一个整形指针变量，到时候这个指针就会变成被删除元素的值，而返回的布尔值则是删除是否成功。毕竟c语言不支持抛出异常，他还想保证鲁棒性的话，就只能这样了。
2、顺序表逆置public void reverse() {
for (int i = 0; i < length / 2; i++) {
int temp = i;
i = arr[length - i - 1];
arr[length - i - 1] = temp;
}
}
这个题说让写成O(1)的算法，我就当场骂娘了，这有for循环啊，你™咋写成O(1)。然后写完了以后看答案，和我写的一样，嗷，原来人家描述问题的单位是这个顺序表，而不是length，那这样写肯定就是一个O(1)算法了。
3、删除某元素public void deleteElem(int x) {
for (int i = 0; i < length; i++) {
if (arr[i] == x) {
for (int j = i; j < length - 1; j++) {
arr[j] = arr[j + 1];
}
length--;
}
}
}
我这个写的有点小复杂了，而且时间复杂度是O(n^2)，这肯定是没分的。
王道的标准答案转写成java应该是这样的：
public void deleteElem(int x) {
int j = 0;
for (int i = 0; i < length; i++) {
if (arr[i] != x) {
arr[j] = arr[i];
j++;
}
}
length = j;
}
4、删除排序顺序内的某开区间内元素
public void deleteInOpenInterval(int s, int t) {
if (length == 0) {
throw new IllegalArgumentException("顺序表长度为0，无法删除元素。");
}
if (s >= t) {
throw new IllegalArgumentException("给出的最小值不小于最大值。不构成区间。");
}
int j = 0;
for (int i = 0; i < length; i++) {
if (s >= arr[i] || arr[i] >= t) {
arr[j] = arr[i];
j++;
}
}
length = j;
}
这是我的写法，我第一次写的时候没注意到居然是有序表，写的有点离谱哈，看答案解析看到说是有序表才点醒我。不过我还没看答案代码，自己再重新写一遍再看吧。
public void deleteInOpenInterval(int s, int t) {
if (length == 0) {
throw new IllegalArgumentException("顺序表长度为0，无法删除元素。");
}
if (s >= t) {
throw new IllegalArgumentException("给出的最小值不小于最大值。不构成区间。");
}
for (int i = 0; i < length; i++) {
if (arr[i] == s) {
s = i;
break;
}
}
for (int i = s + 1; i < length; i++) {
if (arr[i] == t) {
t = i;
break;
}
}
length -= ((t - s) + 1);
for (int i = s + 1; i < length; i++) {
arr[i] = arr[t - s + 1];
}
}
错了，没分。
呜呜呜，应该是删除元素哪里有问题的。看了看王道给的答案，确实，我这个删除的方法有点儿非主流。这样确实容易删错。按照王道的带电啊对这个算法进行改进：
public void deleteInOpenInterval(int s, int t) {
if (length == 0) {
throw new IllegalArgumentException("顺序表长度为0，无法删除元素。");
}
if (s >= t) {
throw new IllegalArgumentException("给出的最小值不小于最大值。不构成区间。");
}
for (int i = 0; i < length; i++) {
if (arr[i] > s) {
s = i;
break;
}
}
for (int i = s + 1; i < length; i++) {
if (arr[i] >= t) {
t = i;
break;
}
}
for (;t < length; s++, t++) {
arr[s] = arr[t];
}
length = s;
}
这样子就好了 -_-||
5、删除顺序表内闭区间元素public void deleteInCloseInterval(int s, int t) {
if (length == 0) {
throw new IllegalArgumentException("顺序表长度为0，无法删除元素。");
}
if (s > t) {
throw new IllegalArgumentException("给出的最小值不小于最大值。不构成区间。");
}
int j = 0;
for (int i = 0; i < length; i++) {
if (arr[i] < s || arr[i] > t) {
arr[j] = arr[i];
j++;
}
}
length = j;
}
王道书上用的不是这个算法，但是也差不多其实，如下：
public void deleteInCloseInterval(int s, int t) {
if (length == 0) {
throw new IllegalArgumentException("顺序表长度为0，无法删除元素。");
}
if (s > t) {
throw new IllegalArgumentException("给出的最小值不小于最大值。不构成区间。");
}
int j = 0;
for (int i = 0; i < length; i++) {
if (s <= arr[i] && arr[i] <= t) {
j++;
} else {
arr[i - j] = arr[i];
}
}
length -= j;
}
这俩其实都是应用了双指针滑动窗口算法。这是顺序表上一个重要的算法。
6、顺序表的去重我能想到的唯一算法就是三层for循环了，可以说是很垃圾了。不管了，先写吧。
public void deleteDuplicate() {
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if (arr[i] == arr[j]) {
length--;
for (int k = j; k < length; k++) {
arr[k] = arr[k + 1];
}
}
}
}
}
虽然这个题没有对时间开销有要求，但这™时间开销都到O(n^3)了，写了个蛇皮棒棒锤啊。
看了下标准答案，不仅鲁棒性比我这个强，而且用到了双指针滑动窗口，所以复杂度也只有O(n)，麻了。
又看了几遍答案解析，发现原来是有序顺序表……以后做题一定要先把有序划出来。这考研题不同于leetcode，不会给你输入输出样例，所以审题一定要好好审题。那我重新写吧。
public void deleteDuplicate() {
if (length == 0) {
throw new IllegalArgumentException("顺序表长度为0，无法删除元素。");
}
int j = 0;
for (int i = 1; i < length; i++) {
if (arr[i] != arr[j]) {
arr[++j] = arr[i];
}
}
length = j + 1;
}
和王道树上的差不多了，强烈建议这段代码要熟练！！！另外多在leetcode上刷一些双指针滑动窗口算法的题。然后我看答案上问就是如果是无序顺序表应该怎么做，还提示说用散列。那咱就试试呗。散列我就直接调用了。
public void deleteDuplicate() {
if (length == 0) {
throw new IllegalArgumentException("顺序表长度为0，无法删除元素。");
}
HashSet set = new HashSet<>();
for (int i = 0, j = 0; i < length; i++) {
if (!set.contains(arr[i])) {
set.add(arr[i]);
arr[j] = arr[i];
j++;
}
}
length = set.size();
}
7、合并两个有序顺序表
public static ArrayList merge(ArrayList l1, ArrayList l2) {
int[] arr = new int[l1.length + l2.length];
for (int i = 0, j = 0, k = 0; i < arr.length; i++) {
if (l1.arr[j] <= l2.arr[k]) {
arr[i] = l1.arr[j];
j++;
} else {
arr[i] = l2.arr[k];
k++;
}
}
return new ArrayList(arr, arr.length);
}
这个不错，O(n)。答案上那个办法能简单点，如下：
public static ArrayList merge(ArrayList l1, ArrayList l2) {
int[] arr = new int[l1.length + l2.length];
int i = 0;
int j = 0;
int k = 0;
while (j < l1.length && k < l2.length) {
if (l1.arr[j] <= l2.arr[k]) {
arr[i++] = l1.arr[j++];
} else {
arr[i++] = l2.arr[k++];
}
}
while (j < l1.length) {
arr[i++] = l1.arr[j++];
}
while (k < l2.length) {
arr[i++] = l2.arr[k++];
}
return new ArrayList(arr, arr.length);
}
就像答案上这样，能用自增的就用自增，显得很简练，很高级。
8、交换顺序表也就是把前m个元素和后n个元素位置打掉头。唉，我又是只能想出复杂度相当高的算法。唉，写吧。
public void swapElem(int m, int n) {
if (m + n != length) {
throw new IllegalArgumentException("长度不匹配");
}
int[] temp;
if (m <= n) {
temp = new int[m];
for (int i = 0; i < m; i++) {
temp[i] = arr[i];
}
for (int i = 0; i < n; i++) {
arr[i] = arr[i + m];
}
for (int i = 0; i < m; i++) {
arr[i + n] = temp[i];
}
} else {
temp = new int[n];
for (int i = 0; i < n; i++) {
temp[i] = arr[i + m];
}
for (int i = m - 1; i >= 0; i--) {
arr[i + n] = arr[i];
}
for (int i = 0; i < n; i++) {
arr[i] = temp[i];
}
}
}
答案上和我这个不一样。思路详见答案。我把他的代码用java实现一遍。
public void swapElem(int m) {
if (m >= length) {
throw new IllegalArgumentException("长度不匹配");
}
reverse(arr, 0, length);
reverse(arr, 0, length - m);
reverse(arr, length - m, length);
}
private static void reverse(int[] arr, int begin, int end) {
for (int i = 0; i < (end - begin) / 2; i++) {
int temp = arr[begin + i];
arr[begin + i] = arr[end - i - 1];
arr[end - i - 1] = temp;
}
}
9、在有序顺序表中查找元素
查找成功则将该元素与其后继交换，否则插入该元素使该表仍然顺序排列。
public void swapOrInsert(int x) {
int low = 0;
int high = length - 1;
int index = 0;
boolean find = false;
while (low <= high) {
index = (low + high) / 2;
if (arr[index] == x) {
find = true;
break;
}
if (arr[index] < x) {
low = index + 1;
}
if (arr[index] > x) {
high = index - 1;
}
}
if (find && index < length - 1) {
int temp = arr[index];
arr[index] = arr[index + 1];
arr[index + 1] = temp;
} else if (!find) {
length++;
for (int i = length - 1; i > low; i--) {
arr[i] = arr[i - 1];
}
arr[low] = x;
}
}
答案上和我写的几乎一样，有一个需要改进的就是，二分查找while里面一定要写else，效率更高。如下：
while (low <= high) {
index = (low + high) / 2;
if (arr[index] == x) {
find = true;
break;
}
if (arr[index] < x) {
low = index + 1;
}
else if (arr[index] > x) {
high = index - 1;
}
}
10、【2010年真题】数组左移
(1) 先将整个数组逆置，变为：(xn-1, xn-2, …, xp+1, xp, xp-1, …, x1, x0)，然后再将前(n-p)和后p个元素分别逆置，就可以得到正确的结果。
(2) Java语言描述：
public static void shiftLeft(int[]r, int p) {
if (r.length == 0) {
return;
}
// 逆置整个数组
reverse(r, 0, r.length);
// 逆置前一部分
reverse(r, 0, r.length - p);
// 逆置后一部分
reverse(r, r.length - p, r.length);
}
private static void reverse(int[] arr, int begin, int end) {
for (int i = 0; i < (end - begin) / 2; i++) {
int temp = arr[begin + i];
arr[begin + i] = arr[end - i - 1];
arr[end - i - 1] = temp;
}
}
(3) 时间复杂度为O(n)。空间复杂度为O(1)
备注：答案跟我这个大同小异，没啥好说的。
11、【2011年真题】两个升序表共同的中位数(1) 首先，升序列表的中位数肯定是他的(length - 1) / 2处元素，两个顺序表的中位数肯定就是先要合并才能求出的，但我们这里实际上用不到专门开辟空间来合并两个列表就可以遍历合并后的列表了。我们可以先算出中位数应该在合并列表中的哪个位置。然后开始遍历，若l1[j] <= l2[k]，则j++并判断此时是否遍历到中位数。若l1[j] > l2[k]，则k++并判断此时是否遍历到中位数。
(2) java语言描述：
public static int finMedianOfTwoList(ArrayList l1, ArrayList l2) {
int pos = (l1.length + l2.length - 1) / 2;
int j = 0, k = 0;
for (int i = 0; i <= pos; i++) {
if (l1.arr[j] <= l2.arr[k]) {
if (i == pos) return l1.arr[j];
j++;
} else {
if (i == pos) return l1.arr[k];
k++;
}
}
return -1;
}
(3) 时间复杂度为O(n)，空间复杂度为O(1)
备注：首先一个是忘记写注释了，对于考研而言，这是很不好的一个习惯。前面的提就不说了，我是从第十个题开始下定决心以后写真题要带注释，结果这个题忘了。另外答案上的方法时间复杂度是O(log2n)，空间复杂度和我这个一样。我需要把答案抄下来并理解。先不写了，去吃午饭。回来看会儿计组，晚上继续。
