wiggle sort

keon · keon · commit 2a417909ae49 · 2016-12-04T18:22:48.000-05:00
diff --git a/array/wiggle_sort.py b/array/wiggle_sort.py
@@ -0,0 +1,14 @@
+
+def wiggle_sort(nums):
+    for i in range(len(nums)):
+        if (i % 2 == 1) == (nums[i-1] > nums[i]):
+            nums[i-1], nums[i] = nums[i], nums[i-1]
+
+if __name__ == "__main__":
+    array = [3, 5, 2, 1, 6, 4]
+
+    print(array)
+    wiggle_sort(array)
+    print(array)
+
+
diff --git a/bfs/shortest_distance_from_all_buildings.py b/bfs/shortest_distance_from_all_buildings.py
@@ -3,47 +3,39 @@
 ## do BFS from each building, and decrement all empty place for every building visit
 ## when grid[i][j] == -b_nums, it means that grid[i][j] are already visited from all b_nums
 ## and use dist to record distances from b_nums
-
 def shortest_distance(grid):
-    """
-    :type grid: List[List[int]]
-    :rtype: int
-    """
-    m = len(grid)
-    n = len(grid[0])
-    if not m or not n:
+    if not grid or not grid[0]:
         return -1
 
-    dist = [[0] * n] * m
-    b_nums = 0
-    for i in range(m):
-        for j in range(n):
-            if grid[i][j]==1: b_nums+=1
-    b_idx = 0
-    for i in range(m):
-        for j in range(n):
-            if grid[i][j]==1:
-                bfs(grid, dist, i, j, b_idx)
-                b_idx -= 1
-    res = []
-    for i in range(m):
-        for j in range(n):
-            if grid[i][j] + b_nums == 0:
-                res.append(dist[i][j])
-    return min(res) if res else -1
+    matrix = [[[0,0] for i in range(len(grid[0]))] for j in range(len(grid))]
+
+    cnt = 0    # count how many building we have visited
+    for i in range(len(grid)):
+        for j in range(len(grid[0])):
+            if grid[i][j] == 1:
+                bfs([i,j], grid, matrix, cnt)
+                cnt += 1
+
+    res = float('inf')
+    for i in range(len(matrix)):
+        for j in range(len(matrix[0])):
+            if matrix[i][j][1]==cnt:
+                res = min(res, matrix[i][j][0])
 
-def bfs(grid, dist, i, j, b_idx):
-    m = len(grid)
-    n = len(grid[0])
-    queue = collections.deque([(i, j, 0)])
-    while queue:
-        i, j, d = queue.popleft()
-        for x,y in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
-            if 0<=x<m and 0<=y<n and grid[x][y] == b_idx:
-                dist[x][y] += d+1
-                grid[x][y] -= 1
-                queue.append((x, y, d+1))
+    return res if res!=float('inf') else -1
 
+def bfs(start, grid, matrix, cnt):
+    q = [(start, 0)]
+    while q:
+        tmp = q.pop(0)
+        po, step = tmp[0], tmp[1]
+        for dp in [(-1,0), (1,0), (0,1), (0,-1)]:
+            i, j = po[0]+dp[0], po[1]+dp[1]
+            # only the position be visited by cnt times will append to queue
+            if 0<=i<len(grid) and 0<=j<len(grid[0]) and matrix[i][j][1]==cnt and grid[i][j]==0:
+                matrix[i][j][0] += step+1
+                matrix[i][j][1] = cnt+1
+                q.append(([i,j], step+1))
 
 grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
 print(shortest_distance(grid))
