本站首页 返回顶部 关于博主

云领未来(有感华为云全连接大会)

云领未来

――有感华为全连接大会主题演讲

早上,有幸观看了华为全连接大会第一场的主题演讲《云领未来》。

演讲开始,华为轮值CEO郭平说了一句很自信的话:世界连接什么的都有,但什么都连接的只有华为。从某种角度看,这话未必言过其实。

接着,描述了云服务市场的发展趋势以及华为的商业模式;之后,通过3个案例讲解了华为云在现实中的应用。 阅读全文 »

(6)找到0和1个数相等的最大子数组

给定一个数组,它的元素是0和1,请找出最大的子数组,使这个子数组的元素中0和1的个数相等。

例如,输入
{ 0, 0, 1, 0, 1, 0, 0 }
输出
Largest subarray is { 0, 1, 0, 1 } or { 1, 0, 1, 0}

 

阅读全文 »

(5)找到和等于给定值的最长子数组

给定一个数组,它有n个元素,元素类型为整形。给定一个值,如果能找出1到多个子数组,使子数组中所有元素的和等于给定值。请求出这个多个子数组中最长的那个子数组。

例如,给定如下数组和值:
A[] = { 5, 6, -5, 5, 3, 5, 3, -2, 0 }
Sum = 8

那么,和为8的子数组有3个,分别是:
{ -5, 5, 3, 5 }
{ 3, 5 }
{ 5, 3 }

其中,最长的子数组是
{ -5, 5, 3, 5 },它的长度为4。
阅读全文 »

(4/500)从有限范围的数组中找出重复元素

给定一个数组,它有n个元素,数组中包含1到n-1这些值。在这个数组中,除了一个元素是重复的,其他元素都只出现了一次。请找出重复的元素。

例如,
输入: { 1, 2, 3, 4, 4 }
输出:The duplicate element is 4

输入:{ 1, 2, 3, 4, 2 }
输出:The duplicate element is 2
阅读全文 »

(3/500)在线性时间内对二进制数组排序

给定一个二进制数组(数组元素是0和1),请对数组进行排序,要求时间复杂度为O(n),空间复杂度为O(1)。输出内容应该是所有的0在前,之后是所有的1。
例如,
输入:{ 1, 0, 1, 0, 1, 0, 0, 1 }
输出:{ 0, 0, 0, 0, 1, 1, 1, 1 }

 

1. 傻瓜式方法

一种简单的方法是计算数组中0的个数(假设为k),然后把数组的前k个元素置为0,其他的置为1。同样道理,也可以计算1的个数(假设为k),然后把前面的k个元素置为1,其他的置为0。二者选一即可。实现方式比较简单,代码就省略了。

 

2. 填充0的另一种想法

和计算0的个数相比,我们可以换种方法。如果当前元素是0,我们可以把0放到下一个可用的位置。在所有的元素都处理了之后, 把其它所有的元素都置为1。

C++语言实现:


#include
using namespace std;

// Function to sort binary array in linear time
int Sort(int A[], int n)
{
// k stores index of next available position
int k = 0;

// do for each element
for (int i = 0; i < n; i++) { // if current element is zero, put 0 at next free // position in the array if (A[i] == 0) A[k++] = 0; } // fill all remaining indexes by 1 for (int i = k; i < n; i++) A[k++] = 1; } // main function int main() { int A[] = { 0, 0, 1, 0,1, 1, 0, 1, 0, 0 }; int n = sizeof(A)/sizeof(A[0]); Sort(A, n); // print the rearranged array for (int i = 0 ; i < n; i++) cout << A[i] << " "; return 0; } [/cpp] java语言实现: [java] class SortBinaryArray { // Function to sort binary array in linear time public static void Sort(int A[], int n) { // k stores index of next available position int k = 0; // do for each element for (int i = 0; i < n; i++) { // if current element is zero, put 0 at next free // position in the array if (A[i] == 0) A[k++] = 0; } // fill all remaining indexes by 1 for (int i = k; i < n; i++) A[k++] = 1; } // main function public static void main (String[] args) { int A[] = { 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 }; int n = A.length; Sort(A, n); // print the rearranged array for (int i = 0 ; i < n; i++) System.out.print(A[i] + " "); } } [/java] 输出: 0 0 0 0 0 0 1 1 1 1

以上两种方案的时间复杂度都是O(n),空间复杂度都是o(1)。

 

3. 基于快速排序分而治之的算法

除了以上两种方法,我们还可以借用快速排序中分而治之的思想。这种方法的关键是使用1作为主元素(pivot element),然后创建一个分区过程,最后的结果就是排好序的。

C++语言实现:


#include
using namespace std;

// Function to sort binary array in linear time
int Partition(int A[], int n)
{
int pivot = 1;
int j = 0;

// each time we encounter a 0, j is incremented and
// 0 is placed before the pivot
for (int i = 0; i < n; i++) { if (A[i] < pivot) { swap(A[i], A[j]); j++; } } } // main function int main() { int A[] = { 1, 0, 0, 0, 1, 0, 1, 1 }; int n = sizeof(A)/sizeof(A[0]); Partition(A, n); // print the rearranged array for (int i = 0 ; i < n; i++) cout << A[i] << " "; return 0; } [/cpp] java语言实现: [java] class SortBinaryArray { // Function to sort binary array in linear time public static void Sort(int A[], int n) { int pivot = 1; int j = 0; // each time we encounter a 0, j is incremented and // 0 is placed before the pivot for (int i = 0; i < n; i++) { if (A[i] < pivot) { // swap (A[i], A[j]) int temp = A[i]; A[i] = A[j]; A[j] = temp; j++; } } } // main function public static void main (String[] args) { int A[] = { 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 }; int n = A.length; Sort(A, n); // print the rearranged array for (int i = 0 ; i < n; i++) System.out.print(A[i] + " "); } } [/java] 输出: 0 0 0 0 0 0 1 1 1 1

尽管以上各种方法时间复杂度是O(n),空间复杂度是O(1),明显第三种方法的时间更少。

 

4. 通过首尾两个索引排序

我还能想到另外一种解决方案,新建两个索引分别指向首尾(head 和 end),向中间聚拢,当head指向的数字不为0,并且end指向的数字不为1时,交换它们的位置,直到head大于或等于end。

闲话少说,上代码。偷一下懒,我就只写Java代码了。


public class SortBinaryArray2 {

// Function to sort binary array in linear time
public static void Sort(int A[], int n)
{
int head = 0;
int end = A.length – 1;

while( head < end ) { while( A[head] == 0 && head < A.length -1 ) { head ++; } while( A[end] == 1 && end > 0 )
{
end –;
}
if( head >= end )
{
break;
}
int temp = A[head];
A[head] = A[end];
A[end] = temp;
}
}

public static void main(String[] args) {
int A[] = { 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 };
int n = A.length;

Sort(A, n);

// print the rearranged array
for (int i = 0 ; i < n; i++) { System.out.print(A[i] + " "); } } } [/java] 这种方法是不是更省时? ^_^

 

练习:
1. 在原方案的基础上修改方案,把1放在前面。
2. 给定一个数组,在线性时间内(时间复杂度为O(n))排序,使所有的偶数排在奇数之前。