list add&remove method

I'm trying to do a method which remove the middle element from list of integer but using recursion , i feel really confused about how to do the base case. when i tried this code the input was [1,3,5]
output became[3,5].

public static void removeMid(ArrayList<Integer> o){
int i=0;
	int low=0;
	int high=o.size()-1;
	int mid=(high+low)/2;
	
	
	if(o.get(i)!=mid)
	return ;
		else if(o.get(i)==mid) {
			o.remove(i);
	System.out.println(o.get(i)); //return mid element
		
	System.out.println(o);
	removeMid(o);
		}}```
	
	

</details>


# 答案1
**得分**: 0

这取决于对“中间元素”是什么的定义。

假设中间元素是位于中间索引位置的元素，你应该使用`List/ArrayList`的方法[`E remove(int index)`](https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html#remove-int-)。

你可能希望将移除限制在输入列表大小为奇数的情况下。
```java
public static void removeMid(ArrayList<Integer> o) {
    if (o.size() > 1 && o.size() % 2 != 0) {
        int removed = o.remove(o.size() / 2);
        System.out.println("removed element: " + removed);
    } else {
        System.out.println("no middle element to remove is available");
    }
}

如果你需要移除一个“中间值”，你可以对输入列表进行排序，然后像之前一样移除位于中间索引位置的元素：

public static void removeMidValue(ArrayList<Integer> o) {
    Collections.sort(o);
    removeMid(o);
}

更新
递归解法包括查找“最小”和“最大”元素，移除它们，递归调用以从剩余列表中移除一个中间值，并在从递归调用返回时恢复“最小”和“最大”值。递归的退出条件是剩余列表只包含一个要移除的元素。

另一个要解决的问题是如何恢复“最小”和“最大”元素 - 可以选择在移除/恢复元素时使用它们的“索引”，或者只需将“最小”和“最大”值重新添加到列表中，从而改变初始顺序。

话虽如此，保持顺序的递归解决方案如下所示：

public static void removeMidRecursive(ArrayList<Integer> o) {
    System.out.println("recursive: " + o);
    if (o.size() % 2 == 0) {
        System.out.println("list size is even, no middle element to remove");
    } else if (o.size() == 1) {
        int mid = o.remove(0);
        System.out.println("removed mid element: " + mid);
    } else {
        // 找到最小和最大元素的索引
        int minId = 0;
        int maxId = 0;
        for (int i = 1; i < o.size(); i++) {
            int val = o.get(i);
            if (val < o.get(minId)) {
                minId = i;
            } else if (val >= o.get(maxId)) {
                maxId = i;
            }
        }

        // 对索引进行排序
        int tMin = Math.min(minId, maxId);
        int tMax = Math.max(minId, maxId);
        // 从较大的索引开始移除并存储值
        // 使用 `E remove(int index)`
        Integer atMax = o.remove(tMax);
        // System.out.printf("removed o[%d]=%d%n", tMax, atMax);
        Integer atMin = o.remove(tMin);
        // System.out.printf("removed o[%d]=%d%n", tMin, atMin);
        
        removeMidRecursive(o);

        // 通过在适当的索引处插入值并进行修正来恢复值
        if (tMin > 0) o.add(tMin - 1, atMin); else o.add(0, atMin);
        if (tMax > 0) o.add(tMax - 1, atMax); else o.add(0, atMax);
        
        System.out.println("restored: " + o);
    }
}

测试：

ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(3, 5, 1, 1, 7, 6, 7));
System.out.println(arr);
removeMidRecursive(arr);
System.out.println(arr);

System.out.println("------------------");

arr = new ArrayList<>(Arrays.asList(6, 4, 1, 4, 2, 1, 4));
System.out.println(arr);
removeMidRecursive(arr);
System.out.println(arr);

输出：

[3, 5, 1, 1, 7, 6, 7]
recursive: [3, 5, 1, 1, 7, 6, 7]
recursive: [3, 5, 1, 7, 6]
recursive: [3, 5, 6]
recursive: [5]
removed mid element: 5
restored: [3, 6]
restored: [3, 1, 7, 6]
restored: [3, 1, 1, 7, 6, 7]
[3, 1, 1, 7, 6, 7]
------------------
[6, 4, 1, 4, 2, 1, 4]
recursive: [6, 4, 1, 4, 2, 1, 4]
recursive: [4, 4, 2, 1, 4]
recursive: [4, 4, 2]
recursive: [4]
removed mid element: 4
restored: [4, 2]
restored: [4, 2, 1, 4]
restored: [6, 1, 4, 2, 1, 4]
[6, 1, 4, 2, 1, 4]

无需保持原始顺序的递归移除要简单得多，它使用另一个List的方法boolean remove(Object item)：

public static void removeMidAndShuffle(ArrayList<Integer> o) {
    if (o.size() % 2 == 0) {
        System.out.println("list size is even, no middle element to remove");
    } else if (o.size() == 1) {
        int mid = o.remove(0);
        System.out.println("removed mid element: " + mid);
    } else {
        Integer min = Integer.MAX_VALUE;
        Integer max = Integer.MIN_VALUE;
        for (Integer x : o) {
            min = Math.min(min, x);
            max = Math.max(max, x);
        }
        o.remove(min);
        o.remove(max);
        removeMidAndShuffle(o);
        o.add(min);
        o.add(max);
    }
}

其输出：

[3, 5, 1, 1, 

<details>
<summary>英文:</summary>

It depends on the definition what is a _middle element_

Assuming that the middle element is the one placed at the middle index, you should use `List/ArrayList`&#39;s method [`E remove(int index)`](https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html#remove-int-).

You may want to restrict removal to the case when the size of the input list is odd.
```java
public static void removeMid(ArrayList&lt;Integer&gt; o) {
    if (o.size() &gt; 1 &amp;&amp; o.size() % 2 != 0) {
        int removed = o.remove(o.size() / 2);
        System.out.println(&quot;removed element: &quot; + removed);
    } else {
        System.out.println(&quot;no middle element to remove is available&quot;);
    }
}

If you need to remove a middle value, you may sort the input list and then remove an element at the middle index as before:

public static void removeMidValue(ArrayList<Integer> o) {
    Collections.sort(o);
    removeMid(o);
}

Update<br/>
Recursive solution consists in finding min and max elements, removing them, calling recursively to remove a mid value from the remaining list, and restoring min and max values upon returning from the recursive call. The exit condition from the recursion is when the remaining list contains only one element to be removed.

Another point to address is how to restore the min and max elements - there are options to use their indexes when removing/restoring the element, or just to add min and max values back to the list thus changing initial order.

That being said, the recursive solution keeping the order may be as follows:

public static void removeMidRecursive(ArrayList<Integer> o) {
    System.out.println("recursive: " + o);
    if (o.size() % 2 == 0) {
        System.out.println("list size is even, no middle element to remove");
    } else if (o.size() == 1) {
        int mid = o.remove(0);
        System.out.println("removed mid element: " + mid);
    } else {
        // find indexes of min and max elements
        int minId = 0;
        int maxId = 0;
        for (int i = 1; i < o.size(); i++) {
            int val = o.get(i);
            if (val < o.get(minId)) {
                minId = i;
            } else if (val >= o.get(maxId)) {
                maxId = i;
            }
        }

        // sort the indexes
        int tMin = Math.min(minId, maxId);
        int tMax = Math.max(minId, maxId);
        // start removing from bigger index and store the value
        // using `E remove(int index)`
        Integer atMax = o.remove(tMax);
        // System.out.printf("removed o[%d]=%d%n", tMax, atMax);
        Integer atMin = o.remove(tMin);
        // System.out.printf("removed o[%d]=%d%n", tMin, atMin);
        
        removeMidRecursive(o);

        // restore the values by insertig at appropriate index with a correction
        if (tMin > 0) o.add(tMin - 1, atMin); else o.add(0, atMin);
        if (tMax > 0) o.add(tMax - 1, atMax); else o.add(0, atMax);
        
        System.out.println("restored: " + o);
    }
}

Test:

ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(3, 5, 1, 1, 7, 6, 7));
System.out.println(arr);
removeMidRecursive(arr);
System.out.println(arr);

System.out.println("------------------");

arr = new ArrayList<>(Arrays.asList(6, 4, 1, 4, 2, 1, 4));
System.out.println(arr);
removeMidRecursive(arr);
System.out.println(arr);

output

[3, 5, 1, 1, 7, 6, 7]
recursive: [3, 5, 1, 1, 7, 6, 7]
recursive: [3, 5, 1, 7, 6]
recursive: [3, 5, 6]
recursive: [5]
removed mid element: 5
restored: [3, 6]
restored: [3, 1, 7, 6]
restored: [3, 1, 1, 7, 6, 7]
[3, 1, 1, 7, 6, 7]
------------------
[6, 4, 1, 4, 2, 1, 4]
recursive: [6, 4, 1, 4, 2, 1, 4]
recursive: [4, 4, 2, 1, 4]
recursive: [4, 4, 2]
recursive: [4]
removed mid element: 4
restored: [4, 2]
restored: [4, 2, 1, 4]
restored: [6, 1, 4, 2, 1, 4]
[6, 1, 4, 2, 1, 4]

Recursive removal without keeping the original order is much simpler, and it is using another List's method boolean remove(Object item):

public static void removeMidAndShuffle(ArrayList<Integer> o) {
    if (o.size() % 2 == 0) {
        System.out.println("list size is even, no middle element to remove");
    } else if (o.size() == 1) {
        int mid = o.remove(0);
        System.out.println("removed mid element: " + mid);
    } else {
        Integer min = Integer.MAX_VALUE;
        Integer max = Integer.MIN_VALUE;
        for (Integer x : o) {
            min = Math.min(min, x);
            max = Math.max(max, x);
        }
        o.remove(min);
        o.remove(max);
        removeMidAndShuffle(o);
        o.add(min);
        o.add(max);
    }
}

Its output:

[3, 5, 1, 1, 7, 6, 7]
removed mid element: 5
[3, 6, 1, 7, 1, 7]
---------
[6, 4, 1, 4, 2, 1, 4]
removed mid element: 4
[2, 4, 1, 4, 1, 6]

Here's a simplest case scenario that "iterates" over the values in the ArrayList via recursion. Note that we have an extra parameter, i, that we are passing to track where we are in the list. This simply removes whatever is in the middle position, based on INDEX. It does not take into account the values that contained with the list:

  public static void main(String[] args) {
ArrayList<Integer> numbers = new ArrayList<Integer>();
numbers.add(1);
numbers.add(3);
numbers.add(5);
System.out.println("Before: " + numbers.toString());
removeMid(numbers, 0);
System.out.println("After: " + numbers.toString());
}
public static void removeMid(ArrayList<Integer> o, int i){
if (o!=null && o.size()>0) {
// you didn't give a clear specification for "middle"
int mid=o.size() / 2; // to the right of middle, for even sized lists 
if (i == mid) {
o.remove(i);
}
else {
removeMid(o, i+1);
}
}
}

Output:

Before: [1, 3, 5]
After: [1, 5]