iOS面试必看经典试题分析

不用临时变量怎么实现两个数据的交换？

方式一：加减法的运算方式求解
new_b = a - b + b = a;
new_a = a + b - a = b;
一个简单的运算方式，最重要的思路就是加减法运算的结合性，第一行代码很关键，a = a - b

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

方式二：异或运算
看这代码可能比较绕，我再拆分一下
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
不难发现，异或有一个重要的规律就是：
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个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？

分析：其实关于异或运算有一个有趣的现象，假设函数f(n)是自然数1，2，3,...,n的所有数的异或，即f(n)=1²3^...n, 那么，任意的n（n为自然数），我们能够很快的计算出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个数进行异或，在与1-1000的异或进行异或。 这是利用异或运算符的基本性质，相同为0，相异为1。
即 x = (1001个数的异或）^ (1²3^...1000)
相同元素异或之后是0，与重复的那个元素再异或，得到的就是重复的那个元素。

举一反三---——示例2
有N个整数，除了其中的两个数只出现一次以外，其余的所有的数都正好出现两次，如何用最快的方法求出只出现一次的两个数，要求空间复杂度是O(1).（这个题目的答案在下篇文章揭晓）

 关于时间复杂度和空间复杂度，可能很多同学不明白，下面做一个我的理解说明。

• 时间复杂度
  时间复杂度简单的理解就是执行语句的条数。如果有循环和递归，则忽略简单语句，直接算循环和递归的语句执行次数。
  举个栗子~~不同时间复杂度的情况
  1、 时间复杂度为O(1)

int x = 1; 

2、时间复杂度为O(n)

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

3、时间复杂度为O(log2n)

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

4、 时间复杂度为O(n2)

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

• 空间复杂度

空间复杂度也很简单的理解为临时变量占用的存储空间。一个简单例子：

//交换两个变量x和y  
int x=1, y=2;  
int temp = x;  
x = y;  
y = temp;

一个临时变量temp，所以空间复杂度为O(1)。