flyingchase

Array 数组

1. 相对于array，ArrayList特点：
   动态改变大小，如果事先知道大小，并且不会改变可以使用Array
   存储需要的空间更多
   编译时检查类型是否正确
   只能保存封装类
   可以通过iterator遍历
   size获取存储元素的个数,array中length获取数组长度
   不支持多维
2. list接口
   add(),get(int index),remove(int index),set(),clear()
   ArrayList类的特点：底层是数组结构，查询快，增删慢；线程不安全，效率高
   Vector类的特点：底层是数组机构，查询快，增删慢；线程安全，效率低
   LinkedList类的特点：底层是链表结构，增删快，查询慢；线程不安全，效率低
   removeall:比较参数collection的对象是否包含，如果包含则删除，复杂度O(n^2)
   clear：将所有元素置为空
3. array操作

memset：Arrays.fill()
sort:Arrays.sort()
bsearch: Arrays.binarySearch() must be sorted

int ind = Arrays.binarySearch(students, 0,N,student);//类中需要重构equals函数和compareTo函数


 public int compareTo(Student student) {
      return sid.compareTo(student.sid);
  }
  @Override
  public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      Student student = (Student) o;
     return Objects.equals(sid, student.sid);
 }
int dir[][]={{1,0},{-1,0},{0,1},{0,-1}};
  	

4. 数组反转
   Collections.reverse(buf);

5. 寻找一个集合的最大元素

6. Arrays.sort()然后取第一个元素

7. Collection.max()

8. 两种复制方法
   System.arraycopy(arr1, 0, arr2, 0, arr1.length);
   arr2 = Arrays.copyOf(arr1, arr1.length * 2);

Tips

右移数组

思路： k%=n;保证 k在数组长度 n 之内

reverse(nums,0,n-k-1);
reverse(nums,n-k,n-1);
reverse(nums,0,n-1);

O(1)删除重复元素

思路：从j=0 i=0开始 i 遍历数组 当两指针指向不相等时候++j; A[j]=A[i];

public int removeDuplicates(int[] A) {
    // return the length of A
    if (A.length==0) return 0;
    int j=0;
    // 不断与下一个元素比较 不同则替换为下一元素
    for (int i=0; i<A.length; i++)
        if (A[i]!=A[j]) A[++j]=A[i];
    return ++j;
}

找到升序的下一个稍大排列

思路：

• 从后向前遍历数组 找到非升序的转折点

• 从转折点向后找 找到转折点后最小的数字 并交换转折点和其后的最小位置 即为下一个稍大的排列

public int[] nextPermutation(int[] nums) {
    int len = nums.length;
    if ( len <= 1)
        return nums;
    int i = len - 1; 
    // 从后向前找到非递增的转折点
    while (i > 0 && nums[i] <= nums[i - 1])
        i --;
    // 区间逆转 将转折点及后续部分逆转
    swapList(nums, i, len - 1);
    if (i != 0) {
        int j = i;
        while (nums[j] <= nums[i - 1]) j++;
        // 找到转折点后稍大的数字并交换位置
        swapItem(nums, j, i-1);
    }
    return nums;
}

全部代码：

public void nextPermutation(int[] A) {
    if(A == null || A.length <= 1) return;
    int i = A.length - 2;
    while(i >= 0 && A[i] >= A[i + 1]) i--; // Find 1st id i that breaks descending order
    if(i >= 0) {                           // If not entirely descending
        int j = A.length - 1;              // Start from the end
        while(A[j] <= A[i]) j--;           // Find rightmost first larger id j
        swap(A, i, j);                     // Switch i and j
    }
    reverse(A, i + 1, A.length - 1);       // Reverse the descending sequence
}

public void swap(int[] A, int i, int j) {
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

public void reverse(int[] A, int i, int j) {
    while(i < j) swap(A, i++, j--);
}