按顺序将元素插入数组

Question

我正在尝试按排序顺序将元素添加到一个数组中。

这是我的代码：

```` ```python ``` ````

public class SortedInsertion {

    public static void main(String[] args) {

        int[] arr=new int[6];
        arr[0]=5;
        arr[1]=6;
        arr[2]=9;
        arr[3]=11;
        System.out.println(Arrays.toString(arr));
        insert(7,arr);


    }

    public static void insert(int val,int[] arr){
        int i;
        for(i=0;i<arr.length-1;i++){

            if(arr[i]>val)
                break;
        }
        for(int k=i;k<arr.length-1;k++){
            arr[k+1]=arr[k];
            arr[i]=val;
        }
        System.out.println(Arrays.toString(arr));


    }

}

我得到的输出是： [5, 6, 9, 11, 0, 0]

[5, 6, 7, 9, 9, 9]

但正确的输出应该是：

5,6,9,11,0,0

5,6,7,9,11,0

- Arun Prakash

---

arr[k+1]=arr[k]; arr[i]=val 会被执行多次（在循环中），因此导致了输出结果。 - TheLostMind

只需使用 System.arraycopy 来移动尾部并腾出空间。这样更快更清晰。 - Boris the Spider

灵感来自于Boris the Spider，使用System.arraycopy实现的解决方案。 - Kaplan

Answer 1

您可以使用数组或集合的binarySearch函数来获取插入新值的位置，需要将该位置之后（如果有）的所有元素向右移动。

int position = Math.abs(Collections.binarySearch(sortedList, key)) - 1;

- yamit3

Answer 2

public class InsertInSortedArray {
        public static void main(String[] args) {
            int arr[] = {5, 6, 9, 11};
            Arrays.sort(arr);
            int k = 7;
            int index = findIndexToBeInserted(arr, k, 0, arr.length - 1);
            ArrayList<Integer> al = new ArrayList<>();
            for (int i : arr)
                al.add(i);

            al.add(index, k);
            for (int i : al)
                System.out.println(i);
        }

    private static int findIndexToBeInserted(int[] arr, int k, int start, int end) {
            if (k == 0)
                return 0;

            int mid = (start + end) / 2;

            if (k > arr[mid] && k < arr[mid + 1])
                return mid + 1;

            if (arr[mid] < k)
                return findIndexToBeInserted(arr, k, mid + 1, end);

            return findIndexToBeInserted(arr, k, start, mid - 1);
        }
    }

- Jay Shah

---

在您的代码中添加一些解释：使用了哪种编程语言，有哪些好处。 - 273K

你不知道Arrays.binarySearch()函数，是吗？ - Kaplan

Answer 3

你的 for 循环存在问题

for(i=0;i<arr.length-1;i++){}

它应该迭代到 i<arr.length。

for(i=0;i<arr.length;i++){}

- Ruchira Gayan Ranaweera

Answer 4

这里。

arr[k+1]=arr[k];

你正在用前一个值覆盖每个下一个数组元素。你应该反转循环并从数组末尾开始移动，将所有元素向前移动，直到找到正确的位置，即：

public static void insert(int val, int[] arr) {
    for(int i = arr.length - 1; i > 0; i--) {
        if (arr[i] == 0) continue; // skip last elements to avoid array index out of bound
        arr[i + 1] = arr[i];       // shift elements forward
        if (arr[i] <= val) {       // if we found the right spot
            arr[i] = val;          // place the new element and
            break;                 // break out the loop
        }
    }
    System.out.println(Arrays.toString(arr));
}

- Alex

---

for(int k=arr.length-1;k>i;k--){ arr[k]=arr[k-1]; }（注：此为程序代码，无法进行语言风格转换） - Arun Prakash

你尝试使用你的解决方案插入数字12吗？提示：**[5, 6, 9, 12, 11, 0]** - Kaplan

Answer 5

将“insert”方法更改如下：

    public static void insert(int val,int[] arr){
      int i;
      for(i=0;i<arr.length-1;i++){
        if(arr[i]>val)
          break;
      }
      for(int k=arr.length-2; k>=i; k--){
        arr[k+1]=arr[k];            
      }
      arr[i]=val;
      System.out.println(Arrays.toString(arr));

    }

- arin1405

---

这需要O(n)的时间复杂度。有人能否编写一个更好的算法？ - wittyurchin

特别是针对大于10的值，它不能正常工作：**[5, 6, 9, 11, 0, 11]** - Kaplan

Answer 6

另一种解决方法是使用列表和collections.sort方法。

List<Integer> list = new ArrayList<Integer>(); 
  for (int i = 0; i < arr.length; i++) { 
  list.add(arr[i]); 
  } 
  list.add(val);

  Collections.sort(list);

 int[] result = list.stream().mapToInt(Integer::intValue).toArray();
 System.out.println(Arrays.toString(result));

希望这个解决方案能够帮助到您。

- Suhas

Answer 7

Java代码,

public static void insertElementInSortedArr(int a[], int val) {

        int n[] = new int[a.length + 1];
        int j = 0;
        boolean isAdded = false;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < val) {
                n[j] = a[i];
                j++;
            } else {
                if (!isAdded) {
                    n[j] = val;
                    j = j + 1;
                    isAdded = true;
                }
                n[j] = a[i];
                j = j + 1;
            }
        }
    }

- Rakesh Chaudhari

Answer 8

您可以使用 arrays.sort() 功能将一个值插入新数组，然后对其进行排序。这是一种绕路的解决方法。例如：

    int num = 10;
    int array[] = {6, 7, 8};
    int copy_array[] = new int[array.length + 1];
    for (int i = 0; i < array.length; i++) {
        copy_array[i] = array[i];
    }
    copy_array[copy_array.length - 1] = given_number;
    Arrays.sort(copy_array);

- Francis

Answer 9

说实话，所讨论的数组并不是像这样排序好的：[0, 0, 5, 6, 9, 11]。
它是一个“零尾”数组：[5, 6, 9, 11, 0, 0]。
因此，要向该数组插入值，需要知道有多少个元素被占用。如果您将此值提供给方法，则其复杂度为O(log n)。否则，需要在插入方法中实现计数。

/**
* @throws ArrayIndexOutOfBoundsException when the array is full and the value to be inserted is greater than the last element
*/
private static void insertToZeroTailedArray(int val, int[] arr) {
    // an O(n) operation to count occupied elements
    int elementsCount = 0;
    for (int i = arr.length - 1; i >= 0; i--) {
        if (arr[i] != 0) {
            elementsCount = i + 1;
            break;
        }
    }

    // binarySearch returns a negative position to insert if the value was not found
    int index = Arrays.binarySearch(arr, 0, elementsCount, val);
    if (index != 0) {
        int pos = index < 0
                ? -index - 1 // val not found, it is need to be inserted at (-index)-1 position
                : index;     // val found but we are going to insert it again

        // shift the array to right and drop last element because of the array bounds
        System.arraycopy(arr, pos, arr, pos + 1, arr.length - pos - 1);
        arr[pos] = val;
    } else {
        // the case when value is found at 0 position
        System.arraycopy(arr, 0, arr, 1, arr.length - 1);
        arr[0] = val;
    }
}

对于一个真正排序的数组，以O(log n)的复杂度完成你所需的操作的另一种方法：

private static void insertToReallySortedArray(int val, int[] arr) {
    int index = Arrays.binarySearch(arr, val);
    if (index != 0) {
        int pos = index < 0 ? -index - 1 : index;
        System.arraycopy(arr, pos, arr, pos + 1, arr.length - pos - 1);
        arr[pos] = val;
    } else {
        System.arraycopy(arr, 0, arr, 1, arr.length - 1);
        arr[0] = val;
    }
}

基于这个很棒的答案。

- Sergey Nemchinov

---

两个缺陷：已存在的值不会被插入，当值大于9时解决方案将出现ArrayIndexOutOfBoundsException。 - Kaplan

Answer 10

不知道已经占用的字段数量，如何完全清楚插入函数应该如何工作？

public static void insert( int n, int occupied, int[] array ) {
  if( n >= array[occupied - 1] )
    array[occupied] = n;
  else
    for( int i = 0; i < array.length; i++ ) {
      int n1 = array[i];
      int n2 = array[i + 1];
      if( n1 > n || n1 < n && n2 >= n ) {
        if( n1 > n ) i--;
        System.arraycopy( array, i + 1, array, i + 2, occupied - i - 1 );
        array[i + 1] = n;
        break;
      }
    }
}

从您上面的示例调用：

…
arr[3]=11;
int occupied = 4;
insert( 7, occupied, arr );  // [5, 6, 7, 9, 11, 0]

如果 occupied >= array.length，则使用 ArrayIndexOutOfBoundsException 进行未经检查的破坏

- Kaplan