不用臨時變量怎么實(shí)現(xiàn)兩個數(shù)據(jù)的交換？

方式一：加減法的運(yùn)算方式求解
new_b = a - b + b = a;
new_a = a + b - a = b;
一個簡單的運(yùn)算方式，最重要的思路就是加減法運(yùn)算的結(jié)合性，第一行代碼很關(guān)鍵，a = a - b

//方式一：加減法運(yùn)算
- (void)func2SwapA:(int)a B:(int)b{
    
    a = a - b;
    b = a + b;
    a = b - a;
    NSLog(@"%d,%d",a,b);
}

方式二：異或運(yùn)算
看這代碼可能比較繞，我再拆分一下
new_b = (a^b)b = a^bb = a^(bb) = a^0 = a
new_a = (a^b)a = a^ba = a^ab = (a^a)b = 0^b = b
不難發(fā)現(xiàn)，異或有一個重要的規(guī)律就是：
x^x = 0,
0^x=x,
則可以推理出a^ba=b

- (void)func1SwapA:(int)a B:(int)b{
    a ^= b;
    b ^= a;
    a ^= b;
    NSLog(@"%d,%d",a,b);
}

舉一反三---——示例1
1-1000放在含有1001個元素的數(shù)組中，只有唯一的一個元素值重復(fù)，其它均只出現(xiàn)一次。每個數(shù)組元素只能訪問一次，設(shè)計一個算法，將它找出來；不用輔助存儲空間，能否設(shè)計一個算法實(shí)現(xiàn)？

分析：其實(shí)關(guān)于異或運(yùn)算有一個有趣的現(xiàn)象，假設(shè)函數(shù)f(n)是自然數(shù)1，2，3,...,n的所有數(shù)的異或，即f(n)=1²3^...n, 那么，任意的n（n為自然數(shù)），我們能夠很快的計算出f(n)的值。

if n == 4*m, then f(n) = n
else if n == 4*m + 1, then f(n) = 1
else if n == 4*m + 2, then f(n) = n+1
else n = 0

本題解題方法：我們可以先將1001個數(shù)進(jìn)行異或，在與1-1000的異或進(jìn)行異或。 這是利用異或運(yùn)算符的基本性質(zhì)，相同為0，相異為1。
即 x = (1001個數(shù)的異或）^ (1²3^...1000)
相同元素異或之后是0，與重復(fù)的那個元素再異或，得到的就是重復(fù)的那個元素。

舉一反三---——示例2
有N個整數(shù)，除了其中的兩個數(shù)只出現(xiàn)一次以外，其余的所有的數(shù)都正好出現(xiàn)兩次，如何用最快的方法求出只出現(xiàn)一次的兩個數(shù)，要求空間復(fù)雜度是O(1).（這個題目的答案在下篇文章揭曉）

 關(guān)于時間復(fù)雜度和空間復(fù)雜度，可能很多同學(xué)不明白，下面做一個我的理解說明。

• 時間復(fù)雜度
  時間復(fù)雜度簡單的理解就是執(zhí)行語句的條數(shù)。如果有循環(huán)和遞歸，則忽略簡單語句，直接算循環(huán)和遞歸的語句執(zhí)行次數(shù)。
  舉個栗子~~不同時間復(fù)雜度的情況
  1、 時間復(fù)雜度為O(1)

int x = 1; 

2、時間復(fù)雜度為O(n)

for(int i=0; i<n; i++) {  
    System.out.println(i);  
}

3、時間復(fù)雜度為O(log2n)

int n = 8, count = 0;;  
for(int i=1; i<=n; i *= 2) {  
    count++;  
} 

4、 時間復(fù)雜度為O(n2)

int n = 8, count = 0;;  
for(int i=1; i<=n; i++) {  
    for(int j=1; j<=n; j++) {  
        count++;  
    }  
} 

• 空間復(fù)雜度

空間復(fù)雜度也很簡單的理解為臨時變量占用的存儲空間。一個簡單例子：

//交換兩個變量x和y  
int x=1, y=2;  
int temp = x;  
x = y;  
y = temp;

一個臨時變量temp，所以空間復(fù)雜度為O(1)。