数据结构(P110)

el/2024/2/25 18:02:58

正数前置


设任意n个整数存放于数组A[1···n]中,请将所有正数排在所有负数前面(要求时间复杂度为O(n))。


#include<stdio.h>
void Arrange(int A[],int t)
//n个整数存于数组A中,本算法将数组中所有正数排在所有负数的前面
{	int i=1,j=t,x;  while(i<j){	while(i<j && A[i]>0) i++;while(i<j && A[j]<0) j--;if(i<j&&A[i]<0&&A[j]>0) {	x=A[i];A[i++]=A[j]; A[j--]=x; }//交换A[i] 与A[j]}for(int j=1;j<=t;j++){printf("%d ",A[j]);}printf("\n");
}
int main()
{int n,x,a[255];printf("请输入数据个数:"); scanf("%d",&n);printf("数据输入:\n");for(int i=1;i<=n;i++){scanf("%d",&a[i]);} Arrange(a,n);return 0;
}

思路:从第一个数(i=1)和最后一个数(j=n)开始双向遍历,如果a[i]为正数那么i++,如果a[j]为负数那么j–,然后在i<j的情况下如果a[i]<0并且a[j]>0然后交换数据。


http://www.ngui.cc/el/4466244.html

相关文章

图的dfs递归(非递归)遍历和bfs遍历(邻接表)

1.深度优先遍历是连通图的一种遍历策略&#xff0e;其基本思想如下: 设x是当前被访问的顶点&#xff0c;在对x做过访问的标记之后&#xff0c;选择一条从x出发的未检测过的边(x,y),若发现顶点y已经访问过了&#xff0c;则重新选择另一条从x出发的未检测过的边&#xff0c;否则沿…

2018HPU暑期集训第四次积分训练赛 K - 方框 题解(图形打印)

2018HPU暑期集训第四次积分训练赛 K - 方框 题解&#xff08;图形打印&#xff09; 思路分析&#xff1a;题目已经明确透露了这道题的解法&#xff1a;就是画框。当 输入的边长 n - 4 > 0 的话&#xff0c;就表示可以在内层继续嵌套一个方框。废话就不多说了&#xff0c;直…

【洛谷】P1067 多项式输出

原题链接&#xff1a;P1067 多项式输出 代码如下&#xff1a; #include <bits/stdc.h>using namespace std;const int MAX 105;int n;int num[MAX]; int main() {int flag;cin >> n;for (int i 0; i < n; i) // 输入多项式的幂次数 cin >> num[i];f…

HDU 2032 杨辉三角

Problem Description 还记得中学时候学过的杨辉三角吗&#xff1f;具体的定义这里不再描述&#xff0c;你可以参考以下的图形&#xff1a; 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 Input 输入数据包含多个测试实例&#xff0c;每个测试实例的输入只包含一个正整数n&…

2058(等差求和)

HDU 2058 The sum problem 等差求和公式: Sn(a1aN)*n/2 (a1a1d(n-1))*n/2 a1*nd(n-1)*n/2; 因为此处公差d1&#xff0c;所以Sna1*n(n-1)*n/2,当从第一项开始算起时&#xff08;因本题首项为1&#xff0c;即a11时&#xff09;&#xff0c;SnM时的项的个数n最多; a11&a…

HDU 2059(dp)

龟兔赛跑 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description 据说在很久很久以前&#xff0c;可怜的兔子经历了人生中最大的打击——赛跑输给乌龟后&#xff0c;心中郁闷&#xff0c;发誓要报仇雪恨&#xff0c;于是…

匈牙利算法 (二分匹配法)

过山车 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10683 Accepted Submission(s): 4699 Problem Description RPG girls今天和大家一起去游乐场玩&#xff0c;终于可以坐上梦寐以求的过山车了。可是&am…

HDU 汉诺塔III

汉诺塔III Problem Description 约19世纪末&#xff0c;在欧州的商店中出售一种智力玩具&#xff0c;在一块铜板上有三根杆&#xff0c;最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上&#xff0c;条件是一次只能移动一…

HDU 小兔的棋盘(卡特兰数)

小兔的棋盘 Problem Description 小兔的叔叔从外面旅游回来给她带来了一个礼物&#xff0c;小兔高兴地跑回自己的房间&#xff0c;拆开一看是一个棋盘&#xff0c;小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0&#xff0c;0)走到终点(n,n)的最短路径数是C(2n,n),…

HDU 2068(错排)

RPG的错排 Problem Description 今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜&#xff0c;第一次猜&#xff1a;R是公主&#xff0c;P是草儿&#xff0c;G是月野兔&#xff1b;第…