左神算法筆記: 1. 認識複雜度、對數器、二分法與異或運算

#algorithem/左神算法/基礎 #sorting #XOR

1. 評估算法優劣的核心标準
   1. 時間複雜度（流程決定）
   2. 額外空間複雜度（流程決定）
   3. 常數項時間（實作細節決定）
2. 常數時間的操作
   1. 算數運算-加減乘除
   2. 位運算（ >>[帶符号右移]/ >>>[不帶符号右移]/ <</ |/ &/ ^）
   3. 指派、比較、自增、子減
   4. 數組尋址
3. 三種排序
   1. 選擇排序：周遊整個數組找最大，放在最後
   2. 冒泡排序：相鄰的兩個數比較誰大誰放在後面
   3. 插入排序：第k次循環的時候，保證k角标之前的數組有序
      • 第k個數字往前冒泡
      • ::資料的初始狀況會影響時間複雜度::
        • 已排好的數組：O(N)
        • 完全反着排的數組：O(N^2) -> 最差情況
4. 對數器(用于測試)
   1. 有一個你想要測的方法a，
   2. 實作一個絕對正确但是複雜度不好的方法b
   3. 實作一個随機樣本産生器
   4. 實作比對的方法
   5. 把方法a和方法b比對很多次來驗證方法a是否正确。

   6. 如果有一個樣本使得比對出錯，列印樣本分析是哪個方法出

      錯

   7. 當樣本數量很多時比對測試依然正确，可以确定方法a已經

      正确。

5. 二分法：建構出一種可以排掉另外一邊的邏輯
   • n * 2 + 1 = ( n << 1) | 1
   • eg. 局部最小數：傳回一個無序的，去重的數組中 比左右的數都小的數
     • 邏輯：通過判斷中間的數和它相鄰的數的大小關系來判斷這兩個數處于遞增段還是遞減段

public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1; // don't exists
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0; // arr[0]号最小
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1; // arr[arr.length -1]号最小
        }
        // 最小值在中間
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
        while (left < right) {
            mdi = (left + right) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }
           

1. 異或運算 ::無進位::相加
   • 異或：相同為0，不同為1
   • 同或：相同為1，不同為0
   • eg1. 不用額外變量交換兩個數

int a = 3;
int b = 10;
a = a ^ b;
b = a ^ b;
a = a ^ b;
           

::注意：使用此方法必須保證要有兩個空間，以下的例子為讓arr[0]變為零::

public static void main(String[] args) {
	int[] arr = {7, 20 , 33};
	// swap(arr, 0, 0); // 結果為{0, 20, 33}，因為交換需要兩個空間，需要一個臨時的空間來存儲兩個數的異或值
	swap(arr, 0, 2);
}
public static void swap(int[] arr, int i, int j) {
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
}
           

- eg2. 一個數組中有一個數出現了奇數次，其他數都出現了偶數次，找到并列印這個數
	- 直接對所有的數做異或運算
- eg3. 保留一個2進制數最右側的1（找到這個1，其餘為填充0）
	- N & (~N + 1)
- eg4. 傳回一個二進制數有多少位是1
	- 根據eg3擷取最右邊的1, rightOne = N & (~N + 1)
	- N ^ rightOne 抹掉最後一位, count++
	- 循環上面兩個步驟
- eg5. 一個數組中有2個數字(a, b)出現了奇數次，其餘數字都出現偶數次，找到這兩個數
	- 第一次異或所有的數 -> eor = a ^ b
	- a != b -> eor != 0 -> eor存在某些位上是1
	- 任取值為1的一位[根據eg3我們能拿到最右側的1]，在這一位上a != b [兩種情況: a = 1, b = 0 或 a = 0, b = 1]
	- 第二次異或所有這一位為1的數 -> eor’ -> eor’ 和eor ^ eor’即為a, b
           

public static void printOddTimesNum2(int[] arr) {
        int eor = 0;
        for (int i : arr) {
            eor ^= i;
        }
        int rightOne = eor & (~eor + 1);
        int eor2 = 0;
        for ( int i : arr) {
            if ((i & rightOne) != 0) { // 最裡面的括号不能省略
                eor2 ^= i;
            }
        }
        System.out.println("第一個數為: " + eor2);
        System.out.println("第二個數為: " + (eor2 ^ eor));
    }